Skip to main content

Find longest increasing path in a matrix

Finding the longest increasing path in a matrix is a problem in computer science that involves finding the longest path in a matrix where each element in the path is greater than the previous element.

In more detail, given an n x m matrix (where n is the number of rows and m is the number of columns), we need to find the length of the longest increasing path in the matrix. An increasing path is defined as a path starting from any cell in the matrix and moving either horizontally or vertically to a neighboring cell with a strictly greater value.

Program Solution

// C program  
// Find longest increasing path in a matrix
#include <stdio.h>

#define ROW 4
#define COL 7
//Print grid elements
void printData(int grid[ROW][COL])
{
	int i = 0;
	int j = 0;
	for (i = 0; i < ROW; ++i)
	{
		for (j = 0; j < COL; ++j)
		{
			printf(" %d\t", grid[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
// Copy visitor element to output collection
void copyResult(int collection[ROW][COL], int visitor[ROW][COL], int output[ROW][COL])
{
	int i = 0;
	int j = 0;
	for (i = 0; i < ROW; ++i)
	{
		for (j = 0; j < COL; ++j)
		{
			// Assign element
			if (visitor[i][j] == 1)
			{
				output[i][j] = collection[i][j];
			}
			else
			{
				output[i][j] = visitor[i][j];
			}
		}
	}
}
// Find increasing path
// r and c is Source point
void findPath(int collection[ROW][COL], int visitor[ROW][COL], int output[ROW][COL], int r, int c, int *length, int counter)
{
	if (r < 0 || r >= ROW || c < 0 || c >= COL)
	{
		//When not valid position
		return;
	}
	if (visitor[r][c] != 0)
	{
		//When the element has been already been visited
		return;
	}
	//Active visiting node
	visitor[r][c] = 1;
	if ( *length < counter)
	{
		// When get new increasing path
		*length = counter;
		copyResult(collection, visitor, output);
	}
	// Test element in 4 direction 
	if (r + 1 < ROW && collection[r + 1][c] > collection[r][c])
	{
		findPath(collection, visitor, output, r + 1, c, length, counter + 1);
	}
	if (c + 1 < COL && collection[r][c + 1] > collection[r][c])
	{
		findPath(collection, visitor, output, r, c + 1, length, counter + 1);
	}
	if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
	{
		findPath(collection, visitor, output, r - 1, c, length, counter + 1);
	}
	if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
	{
		findPath(collection, visitor, output, r, c - 1, length, counter + 1);
	}
	// Deactivate visited node status
	visitor[r][c] = 0;
}
// Handles the request to find longest increasing path
// r and c is Source point
void increasingPath(int collection[ROW][COL], int r, int c)
{
	if (r < 0 || r >= ROW || c < 0 || c >= COL)
	{
		// r and c Source point
		return;
	}
	//Create resultant grid
	int output[ROW][COL];
	int visitor[ROW][COL];
	int i = 0;
	int j = 0;
	int length = 0;
	//Set initial values
	for (i = 0; i < ROW; ++i)
	{
		for (j = 0; j < COL; ++j)
		{
			output[i][j] = 0;
			visitor[i][j] = 0;
		}
	}
	findPath(collection, visitor, output, r, c, & length, 0);
	printf("\n Source point (%d,%d) ", r, c);
	if (length != 0)
	{
		//When result are exist
		// Display solution
		printf("\n Longest Increasing Path \n");
		for (i = 0; i < ROW; ++i)
		{
			for (j = 0; j < COL; ++j)
			{
				if (output[i][j] == 0)
				{
					printf(" - \t");
				}
				else
				{
					printf(" %d\t", output[i][j]);
				}
			}
			printf("\n");
		}
	}
	else
	{
		//When no solution possible
		printf("\n No Increasing Path \n");
	}
}
int main()
{
    int collection[ROW][COL] = 
    { 
        {8,  0,  1, 2,  7, 8,  10},
        {10, 11, 3, 1,  4, 6,   7},
        {21, 19,18, 5, 14, 9,  10},
        {25, 20,17, 16,13, 12, 11}
    }; 
	// Print input problem
	printf("\n Input Matrix \n");
	printData(collection);
	// Test Cases
	increasingPath(collection, 0, 0);
	increasingPath(collection, 1, 3);
	increasingPath(collection, 1, 5);
	increasingPath(collection, 0, 2);
	increasingPath(collection, 0, 4);
	increasingPath(collection, 0, 6);
	return 0;
}

Output

 Input Matrix
 8	 0	 1	 2	 7	 8	 10
 10	 11	 3	 1	 4	 6	 7
 21	 19	 18	 5	 14	 9	 10
 25	 20	 17	 16	 13	 12	 11


 Source point (0,0)
 Longest Increasing Path
 8	 - 	 - 	 - 	 - 	 - 	 -
 10	 11	 - 	 - 	 - 	 - 	 -
 - 	 19	 - 	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (1,3)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 1	 4	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (1,5)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (0,2)
 Longest Increasing Path
 - 	 - 	 1	 - 	 - 	 - 	 -
 - 	 - 	 3	 - 	 - 	 - 	 -
 - 	 19	 18	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (0,4)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 7	 8	 10
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -

 Source point (0,6)
 No Increasing Path
/*
  Java Program for
  Find longest increasing path in a matrix
*/

class Path 
{
  	public int length;
    public Path()
  	{
    	this.length = -1;
    }
    //Print grid elements
    public void printData(int[][] grid, int row, int col)
    {
        int i = 0;
        int j = 0;
        for (i = 0; i < row; ++i)
        {
            for (j = 0; j < col; ++j)
            {
                System.out.print(" " + grid[i][j] + "\t");
            }
            System.out.print("\n");
        }
        System.out.print("\n");
    }
    // Copy visitor element to output collection
    public void copyResult(int[][] collection, boolean[][] visitor, int[][] output, int row, int col)
    {
        int i = 0;
        int j = 0;
        for (i = 0; i < row; ++i)
        {
            for (j = 0; j < col; ++j)
            {
                // Assign element
                if (visitor[i][j] == true)
                {
                    output[i][j] = collection[i][j];
                }
                else
                {
                    output[i][j] = 0;
                }
            }
        }
    }
    // Find increasing path
    // r and c is Source point
    public void findPath(int[][] collection, boolean[][] visitor, 
      int[][] output, int r, int c, int counter, int row,int col)
    {
        if (r < 0 || r >= row || c < 0 || c >= col)
        {
            //When not valid position
            return;
        }
        if (visitor[r][c] == true)
        {
            //When the element has been already been visited
            return;
        }
        //Active visiting node
        visitor[r][c] = true;
        if (this.length < counter)
        {
            // When get new increasing path
            this.length = counter;
            copyResult(collection, visitor, output, row, col);
        }
        // Test element in 4 direction 
        if (r + 1 < row && collection[r + 1][c] > collection[r][c])
        {
            findPath(collection, visitor, output, r + 1, c, counter + 1, row, col);
        }
        if (c + 1 < col && collection[r][c + 1] > collection[r][c])
        {
            findPath(collection, visitor, output, r, c + 1, counter + 1, row, col);
        }
        if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
        {
            findPath(collection, visitor, output, r - 1, c, counter + 1, row, col);
        }
        if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
        {
            findPath(collection, visitor, output, r, c - 1, counter + 1, row, col);
        }
        // Deactivate visited node status
        visitor[r][c] = false;
    }
    // Handles the request to find longest increasing path
    // r and c is Source point
    public void increasingPath(int[][] collection, int r, int c, int row, int col)
    {
        if (r < 0 || r >= row || c < 0 || c >= col)
        {
            // r and c Source point
            return;
        }
        //Create resultant grid
        int[][] output = new int[row][col];
        boolean[][] visitor = new boolean[row][col];
        int i = 0;
        int j = 0;
       this.length = 0;
        //Set initial values
        for (i = 0; i < row; ++i)
        {
            for (j = 0; j < col; ++j)
            {
                output[i][j] = 0;
                visitor[i][j] =false;
            }
        }
        findPath(collection, visitor, output, r, c, 0, row,col);
        System.out.print("\n Source point (" + r + "," + c + ") ");
        if (length != 0)
        {
            //When result are exist
            // Display solution
            System.out.print("\n Longest Increasing Path \n");
            for (i = 0; i < row; ++i)
            {
                for (j = 0; j < col; ++j)
                {
                    if (output[i][j] == 0)
                    {
                        System.out.print(" - \t");
                    }
                    else
                    {
                        System.out.print(" " + output[i][j] + "\t");
                    }
                }
                System.out.print("\n");
            }
        }
        else
        {
            //When no solution possible
            System.out.print("\n No Increasing Path \n");
        }
    }
    public static void main(String[] args) 
    {
        Path task = new Path();
        int [][]collection = 
        { 
            {8,  0,  1, 2,  7, 8,  10},
            {10, 11, 3, 1,  4, 6,   7},
            {21, 19,18, 5, 14, 9,  10},
            {25, 20,17, 16,13, 12, 11}
        }; 
        // Get size
        int row = collection.length;
        int col = collection[0].length;

        // Print input problem
        System.out.print("\n Input Matrix \n");
        task.printData(collection,row,col);
        
        // Test Cases
        task.increasingPath(collection, 0, 0,row,col);
        task.increasingPath(collection, 1, 3,row,col);
        task.increasingPath(collection, 1, 5,row,col);
        task.increasingPath(collection, 0, 2,row,col);
        task.increasingPath(collection, 0, 4,row,col);
        task.increasingPath(collection, 0, 6,row,col);
    }
}

Output

 Input Matrix
 8	 0	 1	 2	 7	 8	 10
 10	 11	 3	 1	 4	 6	 7
 21	 19	 18	 5	 14	 9	 10
 25	 20	 17	 16	 13	 12	 11


 Source point (0,0)
 Longest Increasing Path
 8	 - 	 - 	 - 	 - 	 - 	 -
 10	 11	 - 	 - 	 - 	 - 	 -
 - 	 19	 - 	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (1,3)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 1	 4	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (1,5)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (0,2)
 Longest Increasing Path
 - 	 - 	 1	 - 	 - 	 - 	 -
 - 	 - 	 3	 - 	 - 	 - 	 -
 - 	 19	 18	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (0,4)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 7	 8	 10
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -

 Source point (0,6)
 No Increasing Path
// Include header file
#include <iostream>
#define ROW 4
#define COL 7
using namespace std;
/*
  C++ Program for
  Find longest increasing path in a matrix
*/
class Path
{
	public: int length;
	Path()
	{
		this->length = -1;
	}
	//Print grid elements
	void printData(int grid[ROW][COL])
	{
		int i = 0;
		int j = 0;
		for (i = 0; i < ROW; ++i)
		{
			for (j = 0; j < COL; ++j)
			{
				cout << " " << grid[i][j] << "\t";
			}
			cout << "\n";
		}
		cout << "\n";
	}
	// Copy visitor element to output collection
	void copyResult(int collection[ROW][COL], bool visitor[ROW][COL], int output[ROW][COL])
	{
		int i = 0;
		int j = 0;
		for (i = 0; i < ROW; ++i)
		{
			for (j = 0; j < COL; ++j)
			{
				// Assign element
				if (visitor[i][j] == true)
				{
					output[i][j] = collection[i][j];
				}
				else
				{
					output[i][j] = 0;
				}
			}
		}
	}
	// Find increasing path
	// r and c is Source point
	void findPath(int collection[ROW][COL], bool visitor[ROW][COL], int output[ROW][COL], 
      int r, int c, int counter)
	{
		//When not valid position
		if (r < 0 || r >= ROW || c < 0 || c >= COL)
		{
			return;
		}
		//When the element has been already been visited
		if (visitor[r][c] == true)
		{
			return;
		}
		//Active visiting node
		visitor[r][c] = true;
		if (this->length < counter)
		{
			// When get new increasing path
			this->length = counter;
			this->copyResult(collection, visitor, output);
		}
		// Test element in 4 direction
		if (r + 1 < ROW && collection[r + 1][c] > collection[r][c])
		{
			this->findPath(collection, visitor, output, r + 1, c, counter + 1);
		}
		if (c + 1 < COL && collection[r][c + 1] > collection[r][c])
		{
			this->findPath(collection, visitor, output, r, c + 1, counter + 1);
		}
		if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
		{
			this->findPath(collection, visitor, output, r - 1, c, counter + 1);
		}
		if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
		{
			this->findPath(collection, visitor, output, r, c - 1, counter + 1);
		}
		// Deactivate visited node status
		visitor[r][c] = false;
	}
	// Handles the request to find longest increasing path
	// r and c is Source point
	void increasingPath(int collection[ROW][COL], int r, int c)
	{
		// r and c Source point
		if (r < 0 || r >= ROW || c < 0 || c >= COL)
		{
			return;
		}
		//Create resultant grid
		int output[ROW][COL];
		bool visitor[ROW][COL];
		int i = 0;
		int j = 0;
		this->length = 0;
		//Set initial values
		for (i = 0; i < ROW; ++i)
		{
			for (j = 0; j < COL; ++j)
			{
				output[i][j] = 0;
				visitor[i][j] = false;
			}
		}
		this->findPath(collection, visitor, output, r, c, 0);
		cout << "\n Source point (" << r << "," << c << ") ";
		if (this->length != 0)
		{
			//When result are exist
			// Display solution
			cout << "\n Longest Increasing Path \n";
			for (i = 0; i < ROW; ++i)
			{
				for (j = 0; j < COL; ++j)
				{
					if (output[i][j] == 0)
					{
						cout << " - \t";
					}
					else
					{
						cout << " " << output[i][j] << "\t";
					}
				}
				cout << "\n";
			}
		}
		else
		{
			//When no solution possible
			cout << "\n No Increasing Path \n";
		}
	}
};
int main()
{
	Path task = Path();
	int collection[ROW][COL] =
    { 
        {8,  0,  1, 2,  7, 8,  10},
        {10, 11, 3, 1,  4, 6,   7},
        {21, 19,18, 5, 14, 9,  10},
        {25, 20,17, 16,13, 12, 11}
    }; 

	// Print input problem
	cout << "\n Input Matrix \n";
	task.printData(collection);
	// Test Cases
	task.increasingPath(collection, 0, 0);
	task.increasingPath(collection, 1, 3);
	task.increasingPath(collection, 1, 5);
	task.increasingPath(collection, 0, 2);
	task.increasingPath(collection, 0, 4);
	task.increasingPath(collection, 0, 6);
	return 0;
}

Output

 Input Matrix
 8	 0	 1	 2	 7	 8	 10
 10	 11	 3	 1	 4	 6	 7
 21	 19	 18	 5	 14	 9	 10
 25	 20	 17	 16	 13	 12	 11


 Source point (0,0)
 Longest Increasing Path
 8	 - 	 - 	 - 	 - 	 - 	 -
 10	 11	 - 	 - 	 - 	 - 	 -
 - 	 19	 - 	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (1,3)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 1	 4	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (1,5)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (0,2)
 Longest Increasing Path
 - 	 - 	 1	 - 	 - 	 - 	 -
 - 	 - 	 3	 - 	 - 	 - 	 -
 - 	 19	 18	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (0,4)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 7	 8	 10
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -

 Source point (0,6)
 No Increasing Path
// Include namespace system
using System;
/*
  C# Program for
  Find longest increasing path in a matrix
*/
public class Path
{
	public int length;
	public Path()
	{
		this.length = -1;
	}
	//Print grid elements
	public void printData(int[,] grid, int row, int col)
	{
		int i = 0;
		int j = 0;
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				Console.Write(" " + grid[i,j] + "\t");
			}
			Console.Write("\n");
		}
		Console.Write("\n");
	}
	// Copy visitor element to output collection
	public void copyResult(int[,] collection, Boolean[,] visitor, int[,] output, int row, int col)
	{
		int i = 0;
		int j = 0;
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				// Assign element
				if (visitor[i,j] == true)
				{
					output[i,j] = collection[i,j];
				}
				else
				{
					output[i,j] = 0;
				}
			}
		}
	}
	// Find increasing path
	// r and c is Source point
	public void findPath(int[,] collection, Boolean[,] visitor, int[,] output, int r, int c, int counter, int row, int col)
	{
		//When not valid position
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		//When the element has been already been visited
		if (visitor[r,c] == true)
		{
			return;
		}
		//Active visiting node
		visitor[r,c] = true;
		if (this.length < counter)
		{
			// When get new increasing path
			this.length = counter;
			copyResult(collection, visitor, output, row, col);
		}
		// Test element in 4 direction
		if (r + 1 < row && collection[r + 1,c] > collection[r,c])
		{
			findPath(collection, visitor, output, r + 1, c, counter + 1, row, col);
		}
		if (c + 1 < col && collection[r,c + 1] > collection[r,c])
		{
			findPath(collection, visitor, output, r, c + 1, counter + 1, row, col);
		}
		if (r - 1 >= 0 && collection[r - 1,c] > collection[r,c])
		{
			findPath(collection, visitor, output, r - 1, c, counter + 1, row, col);
		}
		if (c - 1 >= 0 && collection[r,c - 1] > collection[r,c])
		{
			findPath(collection, visitor, output, r, c - 1, counter + 1, row, col);
		}
		// Deactivate visited node status
		visitor[r,c] = false;
	}
	// Handles the request to find longest increasing path
	// r and c is Source point
	public void increasingPath(int[,] collection, int r, int c, int row, int col)
	{
		// r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		//Create resultant grid
		int[,] output = new int[row,col];
		Boolean[,] visitor = new Boolean[row,col];
		int i = 0;
		int j = 0;
		this.length = 0;
		//Set initial values
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				output[i,j] = 0;
				visitor[i,j] = false;
			}
		}
		findPath(collection, visitor, output, r, c, 0, row, col);
		Console.Write("\n Source point (" + r + "," + c + ") ");
		if (length != 0)
		{
			//When result are exist
			// Display solution
			Console.Write("\n Longest Increasing Path \n");
			for (i = 0; i < row; ++i)
			{
				for (j = 0; j < col; ++j)
				{
					if (output[i,j] == 0)
					{
						Console.Write(" - \t");
					}
					else
					{
						Console.Write(" " + output[i,j] + "\t");
					}
				}
				Console.Write("\n");
			}
		}
		else
		{
			//When no solution possible
			Console.Write("\n No Increasing Path \n");
		}
	}
	public static void Main(String[] args)
	{
		Path task = new Path();
		int[,] collection = {
			{
				8 , 0 , 1 , 2 , 7 , 8 , 10
			} , {
				10 , 11 , 3 , 1 , 4 , 6 , 7
			} , {
				21 , 19 , 18 , 5 , 14 , 9 , 10
			} , {
				25 , 20 , 17 , 16 , 13 , 12 , 11
			}
		};
		// Get size
		int row = collection.GetLength(0);
		int col = collection.GetLength(1);
		// Print input problem
		Console.Write("\n Input Matrix \n");
		task.printData(collection, row, col);
		// Test Cases
		task.increasingPath(collection, 0, 0, row, col);
		task.increasingPath(collection, 1, 3, row, col);
		task.increasingPath(collection, 1, 5, row, col);
		task.increasingPath(collection, 0, 2, row, col);
		task.increasingPath(collection, 0, 4, row, col);
		task.increasingPath(collection, 0, 6, row, col);
	}
}

Output

 Input Matrix
 8	 0	 1	 2	 7	 8	 10
 10	 11	 3	 1	 4	 6	 7
 21	 19	 18	 5	 14	 9	 10
 25	 20	 17	 16	 13	 12	 11


 Source point (0,0)
 Longest Increasing Path
 8	 - 	 - 	 - 	 - 	 - 	 -
 10	 11	 - 	 - 	 - 	 - 	 -
 - 	 19	 - 	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (1,3)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 1	 4	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (1,5)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (0,2)
 Longest Increasing Path
 - 	 - 	 1	 - 	 - 	 - 	 -
 - 	 - 	 3	 - 	 - 	 - 	 -
 - 	 19	 18	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (0,4)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 7	 8	 10
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -

 Source point (0,6)
 No Increasing Path
<?php
/*
  Php Program for
  Find longest increasing path in a matrix
*/
class Path
{
	public $length;

	function __construct()
	{
		$this->length = -1;
	}
	//Print grid elements
	public	function printData( & $grid, $row, $col)
	{
		$i = 0;
		$j = 0;
		for ($i = 0; $i < $row; ++$i)
		{
			for ($j = 0; $j < $col; ++$j)
			{
				echo " ". $grid[$i][$j] ."\t";
			}
			echo "\n";
		}
		echo "\n";
	}
	// Copy visitor element to output collection
	public	function copyResult( & $collection, & $visitor, & $output, $row, $col)
	{
		$i = 0;
		$j = 0;
		for ($i = 0; $i < $row; ++$i)
		{
			for ($j = 0; $j < $col; ++$j)
			{
				// Assign element
				if ($visitor[$i][$j] == true)
				{
					$output[$i][$j] = $collection[$i][$j];
				}
				else
				{
					$output[$i][$j] = 0;
				}
			}
		}
	}
	// Find increasing path
	// r and c is Source point
	public	function findPath( & $collection, & $visitor, & $output, $r, $c, $counter, $row, $col)
	{
		//When not valid position
		if ($r < 0 || $r >= $row || $c < 0 || $c >= $col)
		{
			return;
		}
		//When the element has been already been visited
		if ($visitor[$r][$c] == true)
		{
			return;
		}
		//Active visiting node
		$visitor[$r][$c] = true;
		if ($this->length < $counter)
		{
			// When get new increasing path
			$this->length = $counter;
			$this->copyResult($collection, $visitor, $output, $row, $col);
		}
		// Test element in 4 direction
		if ($r + 1 < $row && $collection[$r + 1][$c] > $collection[$r][$c])
		{
			$this->findPath($collection, $visitor, $output, $r + 1, $c, $counter + 1, $row, $col);
		}
		if ($c + 1 < $col && $collection[$r][$c + 1] > $collection[$r][$c])
		{
			$this->findPath($collection, $visitor, $output, $r, $c + 1, $counter + 1, $row, $col);
		}
		if ($r - 1 >= 0 && $collection[$r - 1][$c] > $collection[$r][$c])
		{
			$this->findPath($collection, $visitor, $output, $r - 1, $c, $counter + 1, $row, $col);
		}
		if ($c - 1 >= 0 && $collection[$r][$c - 1] > $collection[$r][$c])
		{
			$this->findPath($collection, $visitor, $output, $r, $c - 1, $counter + 1, $row, $col);
		}
		// Deactivate visited node status
		$visitor[$r][$c] = false;
	}
	// Handles the request to find longest increasing path
	// r and c is Source point
	public	function increasingPath( & $collection, $r, $c, $row, $col)
	{
		// r and c Source point
		if ($r < 0 || $r >= $row || $c < 0 || $c >= $col)
		{
			return;
		}
		$this->length = 0;
		//Create resultant grid
		$output = array_fill(0, $row, array_fill(0, $col, 0));
		$visitor = array_fill(0, $row, array_fill(0, $col, false));
		$i = 0;
		$j = 0;
		$this->findPath($collection, $visitor, $output, $r, $c, 0, $row, $col);
		echo "\n Source point (". $r .",". $c .") ";
		if ($this->length != 0)
		{
			//When result are exist
			// Display solution
			echo "\n Longest Increasing Path \n";
			for ($i = 0; $i < $row; ++$i)
			{
				for ($j = 0; $j < $col; ++$j)
				{
					if ($output[$i][$j] == 0)
					{
						echo " - \t";
					}
					else
					{
						echo " ". $output[$i][$j] ."\t";
					}
				}
				echo "\n";
			}
		}
		else
		{
			//When no solution possible
			echo "\n No Increasing Path \n";
		}
	}
}

function main()
{
	$task = new Path();
	$collection = array(
      array(8, 0, 1, 2, 7, 8, 10), 
      array(10, 11, 3, 1, 4, 6, 7), 
      array(21, 19, 18, 5, 14, 9, 10), 
      array(25, 20, 17, 16, 13, 12, 11));
	// Get size
	$row = count($collection);
	$col = count($collection[0]);
	// Print input problem
	echo "\n Input Matrix \n";
	$task->printData($collection, $row, $col);
	// Test Cases
	$task->increasingPath($collection, 0, 0, $row, $col);
	$task->increasingPath($collection, 1, 3, $row, $col);
	$task->increasingPath($collection, 1, 5, $row, $col);
	$task->increasingPath($collection, 0, 2, $row, $col);
	$task->increasingPath($collection, 0, 4, $row, $col);
	$task->increasingPath($collection, 0, 6, $row, $col);
}
main();

Output

 Input Matrix
 8	 0	 1	 2	 7	 8	 10
 10	 11	 3	 1	 4	 6	 7
 21	 19	 18	 5	 14	 9	 10
 25	 20	 17	 16	 13	 12	 11


 Source point (0,0)
 Longest Increasing Path
 8	 - 	 - 	 - 	 - 	 - 	 -
 10	 11	 - 	 - 	 - 	 - 	 -
 - 	 19	 - 	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (1,3)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 1	 4	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (1,5)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (0,2)
 Longest Increasing Path
 - 	 - 	 1	 - 	 - 	 - 	 -
 - 	 - 	 3	 - 	 - 	 - 	 -
 - 	 19	 18	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (0,4)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 7	 8	 10
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -

 Source point (0,6)
 No Increasing Path
/*
  Node Js Program for
  Find longest increasing path in a matrix
*/
class Path
{
	constructor()
	{
		this.length = -1;
	}
	//Print grid elements
	printData(grid, row, col)
	{
		var i = 0;
		var j = 0;
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				process.stdout.write(" " + grid[i][j] + "\t");
			}
			process.stdout.write("\n");
		}
		process.stdout.write("\n");
	}
	// Copy visitor element to output collection
	copyResult(collection, visitor, output, row, col)
	{
		var i = 0;
		var j = 0;
		for (i = 0; i < row; ++i)
		{
			for (j = 0; j < col; ++j)
			{
				// Assign element
				if (visitor[i][j] == true)
				{
					output[i][j] = collection[i][j];
				}
				else
				{
					output[i][j] = 0;
				}
			}
		}
	}
	// Find increasing path
	// r and c is Source point
	findPath(collection, visitor, output, r, c, counter, row, col)
	{
		//When not valid position
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		//When the element has been already been visited
		if (visitor[r][c] == true)
		{
			return;
		}
		//Active visiting node
		visitor[r][c] = true;
		if (this.length < counter)
		{
			// When get new increasing path
			this.length = counter;
			this.copyResult(collection, visitor, output, row, col);
		}
		// Test element in 4 direction
		if (r + 1 < row && collection[r + 1][c] > collection[r][c])
		{
			this.findPath(collection, visitor, output, r + 1, c, counter + 1, row, col);
		}
		if (c + 1 < col && collection[r][c + 1] > collection[r][c])
		{
			this.findPath(collection, visitor, output, r, c + 1, counter + 1, row, col);
		}
		if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
		{
			this.findPath(collection, visitor, output, r - 1, c, counter + 1, row, col);
		}
		if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
		{
			this.findPath(collection, visitor, output, r, c - 1, counter + 1, row, col);
		}
		// Deactivate visited node status
		visitor[r][c] = false;
	}
	// Handles the request to find longest increasing path
	// r and c is Source point
	increasingPath(collection, r, c, row, col)
	{
		// r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		this.length = 0;
		//Create resultant grid
		var output = Array(row).fill(0).map(() => new Array(col).fill(0));
		var visitor = Array(row).fill(false).map(() => new Array(col).fill(false));
		var i = 0;
		var j = 0;
		this.findPath(collection, visitor, output, r, c, 0, row, col);
		process.stdout.write("\n Source point (" + r + "," + c + ") ");
		if (this.length != 0)
		{
			//When result are exist
			// Display solution
			process.stdout.write("\n Longest Increasing Path \n");
			for (i = 0; i < row; ++i)
			{
				for (j = 0; j < col; ++j)
				{
					if (output[i][j] == 0)
					{
						process.stdout.write(" - \t");
					}
					else
					{
						process.stdout.write(" " + output[i][j] + "\t");
					}
				}
				process.stdout.write("\n");
			}
		}
		else
		{
			//When no solution possible
			process.stdout.write("\n No Increasing Path \n");
		}
	}
}

function main()
{
	var task = new Path();
	var collection = [
	  [8, 0, 1, 2, 7, 8, 10] , 
      [10, 11, 3, 1, 4, 6, 7] , 
      [21, 19, 18, 5, 14, 9, 10] , 
      [25, 20, 17, 16, 13, 12, 11]
	];
	// Get size
	var row = collection.length;
	var col = collection[0].length;
	// Print input problem
	process.stdout.write("\n Input Matrix \n");
	task.printData(collection, row, col);
	// Test Cases
	task.increasingPath(collection, 0, 0, row, col);
	task.increasingPath(collection, 1, 3, row, col);
	task.increasingPath(collection, 1, 5, row, col);
	task.increasingPath(collection, 0, 2, row, col);
	task.increasingPath(collection, 0, 4, row, col);
	task.increasingPath(collection, 0, 6, row, col);
}
main();

Output

 Input Matrix
 8	 0	 1	 2	 7	 8	 10
 10	 11	 3	 1	 4	 6	 7
 21	 19	 18	 5	 14	 9	 10
 25	 20	 17	 16	 13	 12	 11


 Source point (0,0)
 Longest Increasing Path
 8	 - 	 - 	 - 	 - 	 - 	 -
 10	 11	 - 	 - 	 - 	 - 	 -
 - 	 19	 - 	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (1,3)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 1	 4	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (1,5)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (0,2)
 Longest Increasing Path
 - 	 - 	 1	 - 	 - 	 - 	 -
 - 	 - 	 3	 - 	 - 	 - 	 -
 - 	 19	 18	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (0,4)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 7	 8	 10
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -

 Source point (0,6)
 No Increasing Path
#   Python 3 Program for
#   Find longest increasing path in a matrix

class Path :
	
	def __init__(self) :
		self.length = -1
	
	# Print grid elements
	def printData(self, grid, row, col) :
		i = 0
		j = 0
		while (i < row) :
			j = 0
			while (j < col) :
				print("", grid[i][j] , end = "\t")
				j += 1
			
			print(end = "\n")
			i += 1
		
		print(end = "\n")
	
	#  Copy visitor element to output collection
	def copyResult(self, collection, visitor, output, row, col) :
		i = 0
		j = 0
		while (i < row) :
			j = 0
			while (j < col) :
				#  Assign element
				if (visitor[i][j] == True) :
					output[i][j] = collection[i][j]
				else :
					output[i][j] = 0
				
				j += 1
			
			i += 1
		
	
	#  Find increasing path
	#  r and c is Source point
	def findPath(self, collection, visitor, output, r, c, counter, row, col) :
		# When not valid position
		if (r < 0 or r >= row or c < 0 or c >= col) :
			return
		
		# When the element has been already been visited
		if (visitor[r][c] == True) :
			return
		
		# Active visiting node
		visitor[r][c] = True
		if (self.length < counter) :
			#  When get new increasing path
			self.length = counter
			self.copyResult(collection, visitor, output, row, col)
		
		#  Test element in 4 direction
		if (r + 1 < row and collection[r + 1][c] > collection[r][c]) :
			self.findPath(collection, visitor, output, r + 1, c, counter + 1, row, col)
		
		if (c + 1 < col and collection[r][c + 1] > collection[r][c]) :
			self.findPath(collection, visitor, output, r, c + 1, counter + 1, row, col)
		
		if (r - 1 >= 0 and collection[r - 1][c] > collection[r][c]) :
			self.findPath(collection, visitor, output, r - 1, c, counter + 1, row, col)
		
		if (c - 1 >= 0 and collection[r][c - 1] > collection[r][c]) :
			self.findPath(collection, visitor, output, r, c - 1, counter + 1, row, col)
		
		#  Deactivate visited node status
		visitor[r][c] = False
	
	#  Handles the request to find longest increasing path
	#  r and c is Source point
	def increasingPath(self, collection, r, c, row, col) :
		#  r and c Source point
		if (r < 0 or r >= row or c < 0 or c >= col) :
			return
		
		self.length = 0
		# Create resultant grid
		output = [[0] * (col) for _ in range(row) ]
		visitor = [[False] * (col) for _ in range(row) ]
		self.findPath(collection, visitor, output, r, c, 0, row, col)
		print("\n Source point (", r ,",", c ,") ", end = "")
		if (self.length != 0) :
			# When result are exist
			i = 0
			j = 0
			#  Display solution
			print("\n Longest Increasing Path ")
			while (i < row) :
				j = 0
				while (j < col) :
					if (output[i][j] == 0) :
						print(end = "-\t")
					else :
						print(output[i][j], end = "\t")
					
					j += 1
				
				print(end = "\n")
				i += 1
			
		else :
			# When no solution possible
			print("\n No Increasing Path ")
		
	

def main() :
	task = Path()
	collection = [
		[8, 0, 1, 2, 7, 8, 10] , 
      [10, 11, 3, 1, 4, 6, 7] , 
      [21, 19, 18, 5, 14, 9, 10] , 
      [25, 20, 17, 16, 13, 12, 11]
	]
	#  Get size
	row = len(collection)
	col = len(collection[0])
	#  Print input problem
	print("\n Input Matrix ")
	task.printData(collection, row, col)
	#  Test Cases
	task.increasingPath(collection, 0, 0, row, col)
	task.increasingPath(collection, 1, 3, row, col)
	task.increasingPath(collection, 1, 5, row, col)
	task.increasingPath(collection, 0, 2, row, col)
	task.increasingPath(collection, 0, 4, row, col)
	task.increasingPath(collection, 0, 6, row, col)

if __name__ == "__main__": main()

Output

 Input Matrix
 8	 0	 1	 2	 7	 8	 10
 10	 11	 3	 1	 4	 6	 7
 21	 19	 18	 5	 14	 9	 10
 25	 20	 17	 16	 13	 12	 11


 Source point ( 0 , 0 )
 Longest Increasing Path
8	-	-	-	-	-	-
10	11	-	-	-	-	-
-	19	-	-	-	-	-
25	20	-	-	-	-	-

 Source point ( 1 , 3 )
 Longest Increasing Path
-	-	-	-	-	-	-
-	-	-	1	4	6	-
-	19	18	-	-	9	10
25	20	17	16	13	12	11

 Source point ( 1 , 5 )
 Longest Increasing Path
-	-	-	-	-	-	-
-	-	-	-	-	6	-
-	19	18	-	-	9	10
25	20	17	16	13	12	11

 Source point ( 0 , 2 )
 Longest Increasing Path
-	-	1	-	-	-	-
-	-	3	-	-	-	-
-	19	18	-	-	-	-
25	20	-	-	-	-	-

 Source point ( 0 , 4 )
 Longest Increasing Path
-	-	-	-	7	8	10
-	-	-	-	-	-	-
-	-	-	-	-	-	-
-	-	-	-	-	-	-

 Source point ( 0 , 6 )
 No Increasing Path
#   Ruby Program for
#   Find longest increasing path in a matrix

class Path  
	# Define the accessor and reader of class Path  
	attr_reader :length
	attr_accessor :length
 
	
	def initialize() 
		self.length = -1
	end

	# Print grid elements
	def printData(grid, row, col) 
		i = 0
		j = 0
		while (i < row) 
			j = 0
			while (j < col) 
				print(" ", grid[i][j] ,"\t")
				j += 1
			end

			print("\n")
			i += 1
		end

		print("\n")
	end

	#  Copy visitor element to output collection
	def copyResult(collection, visitor, output, row, col) 
		i = 0
		j = 0
		while (i < row) 
			j = 0
			while (j < col) 
				#  Assign element
				if (visitor[i][j] == true) 
					output[i][j] = collection[i][j]
				else 
					output[i][j] = 0
				end

				j += 1
			end

			i += 1
		end

	end

	#  Find increasing path
	#  r and c is Source point
	def findPath(collection, visitor, output, r, c, counter, row, col) 
		# When not valid position
		if (r < 0 || r >= row || c < 0 || c >= col) 
			return
		end

		# When the element has been already been visited
		if (visitor[r][c] == true) 
			return
		end

		# Active visiting node
		visitor[r][c] = true
		if (self.length < counter) 
			#  When get new increasing path
			self.length = counter
			self.copyResult(collection, visitor, output, row, col)
		end

		#  Test element in 4 direction
		if (r + 1 < row && collection[r + 1][c] > collection[r][c]) 
			self.findPath(collection, visitor, output, r + 1, c, counter + 1, row, col)
		end

		if (c + 1 < col && collection[r][c + 1] > collection[r][c]) 
			self.findPath(collection, visitor, output, r, c + 1, counter + 1, row, col)
		end

		if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c]) 
			self.findPath(collection, visitor, output, r - 1, c, counter + 1, row, col)
		end

		if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c]) 
			self.findPath(collection, visitor, output, r, c - 1, counter + 1, row, col)
		end

		#  Deactivate visited node status
		visitor[r][c] = false
	end

	#  Handles the request to find longest increasing path
	#  r and c is Source point
	def increasingPath(collection, r, c, row, col) 
		#  r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col) 
			return
		end

		self.length = 0
		# Create resultant grid
		output = Array.new(row) {Array.new(col) {0}}
		visitor = Array.new(row) {Array.new(col) {false}}
		self.findPath(collection, visitor, output, r, c, 0, row, col)
		print("\n Source point (", r ,",", c ,") ")
		if (self.length != 0) 
			# When result are exist
			i = 0
			j = 0
			#  Display solution
			print("\n Longest Increasing Path \n")
			while (i < row) 
				j = 0
				while (j < col) 
					if (output[i][j] == 0) 
						print(" - \t")
					else 
						print(" ", output[i][j] ,"\t")
					end

					j += 1
				end

				print("\n")
				i += 1
			end

		else 
			# When no solution possible
			print("\n No Increasing Path \n")
		end

	end

end

def main() 
	task = Path.new()
	collection = [
		[8, 0, 1, 2, 7, 8, 10] , [10, 11, 3, 1, 4, 6, 7] , [21, 19, 18, 5, 14, 9, 10] , [25, 20, 17, 16, 13, 12, 11]
	]
	#  Get size
	row = collection.length
	col = collection[0].length
	#  Print input problem
	print("\n Input Matrix \n")
	task.printData(collection, row, col)
	#  Test Cases
	task.increasingPath(collection, 0, 0, row, col)
	task.increasingPath(collection, 1, 3, row, col)
	task.increasingPath(collection, 1, 5, row, col)
	task.increasingPath(collection, 0, 2, row, col)
	task.increasingPath(collection, 0, 4, row, col)
	task.increasingPath(collection, 0, 6, row, col)
end

main()

Output

 Input Matrix 
 8	 0	 1	 2	 7	 8	 10	
 10	 11	 3	 1	 4	 6	 7	
 21	 19	 18	 5	 14	 9	 10	
 25	 20	 17	 16	 13	 12	 11	


 Source point (0,0) 
 Longest Increasing Path 
 8	 - 	 - 	 - 	 - 	 - 	 - 	
 10	 11	 - 	 - 	 - 	 - 	 - 	
 - 	 19	 - 	 - 	 - 	 - 	 - 	
 25	 20	 - 	 - 	 - 	 - 	 - 	

 Source point (1,3) 
 Longest Increasing Path 
 - 	 - 	 - 	 - 	 - 	 - 	 - 	
 - 	 - 	 - 	 1	 4	 6	 - 	
 - 	 19	 18	 - 	 - 	 9	 10	
 25	 20	 17	 16	 13	 12	 11	

 Source point (1,5) 
 Longest Increasing Path 
 - 	 - 	 - 	 - 	 - 	 - 	 - 	
 - 	 - 	 - 	 - 	 - 	 6	 - 	
 - 	 19	 18	 - 	 - 	 9	 10	
 25	 20	 17	 16	 13	 12	 11	

 Source point (0,2) 
 Longest Increasing Path 
 - 	 - 	 1	 - 	 - 	 - 	 - 	
 - 	 - 	 3	 - 	 - 	 - 	 - 	
 - 	 19	 18	 - 	 - 	 - 	 - 	
 25	 20	 - 	 - 	 - 	 - 	 - 	

 Source point (0,4) 
 Longest Increasing Path 
 - 	 - 	 - 	 - 	 7	 8	 10	
 - 	 - 	 - 	 - 	 - 	 - 	 - 	
 - 	 - 	 - 	 - 	 - 	 - 	 - 	
 - 	 - 	 - 	 - 	 - 	 - 	 - 	

 Source point (0,6) 
 No Increasing Path 

/*
  Scala Program for
  Find longest increasing path in a matrix
*/
class Path(var length: Int)
{
	def this()
	{
		this(-1);
	}
	//Print grid elements
	def printData(grid: Array[Array[Int]], row: Int, col: Int): Unit = {
		var i: Int = 0;
		var j: Int = 0;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				print(" " + grid(i)(j) + "\t");
				j += 1;
			}
			print("\n");
			i += 1;
		}
		print("\n");
	}
	// Copy visitor element to output collection
	def copyResult(collection: Array[Array[Int]], visitor: Array[Array[Boolean]], output: Array[Array[Int]], row: Int, col: Int): Unit = {
		var i: Int = 0;
		var j: Int = 0;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				// Assign element
				if (visitor(i)(j) == true)
				{
					output(i)(j) = collection(i)(j);
				}
				else
				{
					output(i)(j) = 0;
				}
				j += 1;
			}
			i += 1;
		}
	}
	// Find increasing path
	// r and c is Source point
	def findPath(collection: Array[Array[Int]], visitor: Array[Array[Boolean]], output: Array[Array[Int]], r: Int, c: Int, counter: Int, row: Int, col: Int): Unit = {
		//When not valid position
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		//When the element has been already been visited
		if (visitor(r)(c) == true)
		{
			return;
		}
		//Active visiting node
		visitor(r)(c) = true;
		if (this.length < counter)
		{
			// When get new increasing path
			this.length = counter;
			this.copyResult(collection, visitor, output, row, col);
		}
		// Test element in 4 direction
		if (r + 1 < row && collection(r + 1)(c) > collection(r)(c))
		{
			this.findPath(collection, visitor, output, r + 1, c, counter + 1, row, col);
		}
		if (c + 1 < col && collection(r)(c + 1) > collection(r)(c))
		{
			this.findPath(collection, visitor, output, r, c + 1, counter + 1, row, col);
		}
		if (r - 1 >= 0 && collection(r - 1)(c) > collection(r)(c))
		{
			this.findPath(collection, visitor, output, r - 1, c, counter + 1, row, col);
		}
		if (c - 1 >= 0 && collection(r)(c - 1) > collection(r)(c))
		{
			this.findPath(collection, visitor, output, r, c - 1, counter + 1, row, col);
		}
		// Deactivate visited node status
		visitor(r)(c) = false;
	}
	// Handles the request to find longest increasing path
	// r and c is Source point
	def increasingPath(collection: Array[Array[Int]], r: Int, c: Int, row: Int, col: Int): Unit = {
		// r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		this.length = 0;
		//Create resultant grid
		var output: Array[Array[Int]] = Array.fill[Int](row, col)(0);
		var visitor: Array[Array[Boolean]] = Array.fill[Boolean](row, col)(false);
		this.findPath(collection, visitor, output, r, c, 0, row, col);
		print("\n Source point (" + r + "," + c + ") ");
		if (this.length != 0)
		{
			//When result are exist
			var i: Int = 0;
			var j: Int = 0;
			// Display solution
			print("\n Longest Increasing Path \n");
			while (i < row)
			{
				j = 0;
				while (j < col)
				{
					if (output(i)(j) == 0)
					{
						print(" - \t");
					}
					else
					{
						print(" " + output(i)(j) + "\t");
					}
					j += 1;
				}
				print("\n");
				i += 1;
			}
		}
		else
		{
			//When no solution possible
			print("\n No Increasing Path \n");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Path = new Path();
		var collection: Array[Array[Int]] = Array(
          Array(8, 0, 1, 2, 7, 8, 10), 
          Array(10, 11, 3, 1, 4, 6, 7), 
          Array(21, 19, 18, 5, 14, 9, 10), 
          Array(25, 20, 17, 16, 13, 12, 11)
        );
		// Get size
		var row: Int = collection.length;
		var col: Int = collection(0).length;
		// Print input problem
		print("\n Input Matrix \n");
		task.printData(collection, row, col);
		// Test Cases
		task.increasingPath(collection, 0, 0, row, col);
		task.increasingPath(collection, 1, 3, row, col);
		task.increasingPath(collection, 1, 5, row, col);
		task.increasingPath(collection, 0, 2, row, col);
		task.increasingPath(collection, 0, 4, row, col);
		task.increasingPath(collection, 0, 6, row, col);
	}
}

Output

 Input Matrix
 8	 0	 1	 2	 7	 8	 10
 10	 11	 3	 1	 4	 6	 7
 21	 19	 18	 5	 14	 9	 10
 25	 20	 17	 16	 13	 12	 11


 Source point (0,0)
 Longest Increasing Path
 8	 - 	 - 	 - 	 - 	 - 	 -
 10	 11	 - 	 - 	 - 	 - 	 -
 - 	 19	 - 	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (1,3)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 1	 4	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (1,5)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (0,2)
 Longest Increasing Path
 - 	 - 	 1	 - 	 - 	 - 	 -
 - 	 - 	 3	 - 	 - 	 - 	 -
 - 	 19	 18	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (0,4)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 7	 8	 10
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -

 Source point (0,6)
 No Increasing Path
/*
  Swift 4 Program for
  Find longest increasing path in a matrix
*/
class Path
{
	var length: Int;
	init()
	{
		self.length = -1;
	}
	//Print grid elements
	func printData(_ grid: [[Int]], _ row: Int, _ col: Int)
	{
		var i: Int = 0;
		var j: Int = 0;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				print("", grid[i][j] , terminator: "\t");
				j += 1;
			}
			print(terminator: "\n");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Copy visitor element to output collection
	func copyResult(_ collection: [[Int]], _ visitor: [[Bool]], _ output: inout[[Int]], _ row: Int, _ col: Int)
	{
		var i: Int = 0;
		var j: Int = 0;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				// Assign element
				if (visitor[i][j] == true)
				{
					output[i][j] = collection[i][j];
				}
				else
				{
					output[i][j] = 0;
				}
				j += 1;
			}
			i += 1;
		}
	}
	// Find increasing path
	// r and c is Source point
	func findPath(_ collection: [[Int]], _ visitor: inout[[Bool]], _ output: inout[[Int]],
      _ r: Int, _ c: Int, _ counter: Int, _ row: Int, _ col: Int)
	{
		//When not valid position
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		//When the element has been already been visited
		if (visitor[r][c] == true)
		{
			return;
		}
		//Active visiting node
		visitor[r][c] = true;
		if (self.length < counter)
		{
			// When get new increasing path
			self.length = counter;
			self.copyResult(collection, visitor, &output, row, col);
		}
		// Test element in 4 direction
		if (r + 1 < row && collection[r + 1][c] > collection[r][c])
		{
			self.findPath(collection, &visitor, &output, r + 1, c, counter + 1, row, col);
		}
		if (c + 1 < col && collection[r][c + 1] > collection[r][c])
		{
			self.findPath(collection, &visitor, &output, r, c + 1, counter + 1, row, col);
		}
		if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
		{
			self.findPath(collection, &visitor, &output, r - 1, c, counter + 1, row, col);
		}
		if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
		{
			self.findPath(collection, &visitor, &output, r, c - 1, counter + 1, row, col);
		}
		// Deactivate visited node status
		visitor[r][c] = false;
	}
	// Handles the request to find longest increasing path
	// r and c is Source point
	func increasingPath(_ collection: [[Int]], _ r: Int, _ c: Int, _ row: Int, _ col: Int)
	{
		// r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		self.length = 0;
		//Create resultant grid
		var output: [[Int]] = Array(repeating: Array(repeating: 0, count: col), count: row);
		var visitor: [[Bool]] = Array(repeating: Array(repeating: false, count: col), count: row);
		self.findPath(collection, &visitor, &output, r, c, 0, row, col);
		print("\n Source point (", r ,",", c ,") ", terminator: "");
		if (self.length  != 0)
		{
			//When result are exist
			var i: Int = 0;
			var j: Int = 0;
			// Display solution
			print("\n Longest Increasing Path ");
			while (i < row)
			{
				j = 0;
				while (j < col)
				{
					if (output[i][j] == 0)
					{
						print(terminator: "-\t");
					}
					else
					{
						print("", output[i][j],terminator: "\t");
					}
					j += 1;
				}
				print(terminator: "\n");
				i += 1;
			}
		}
		else
		{
			//When no solution possible
			print("\n No Increasing Path ");
		}
	}
}
func main()
{
	let task: Path = Path();
	let collection: [[Int]] = [
		[8, 0, 1, 2, 7, 8, 10] , 
      [10, 11, 3, 1, 4, 6, 7] , 
      [21, 19, 18, 5, 14, 9, 10] , 
      [25, 20, 17, 16, 13, 12, 11]
	];
	// Get size
	let row: Int = collection.count;
	let col: Int = collection[0].count;
	// Print input problem
	print("\n Input Matrix ");
	task.printData(collection, row, col);
	// Test Cases
	task.increasingPath(collection, 0, 0, row, col);
	task.increasingPath(collection, 1, 3, row, col);
	task.increasingPath(collection, 1, 5, row, col);
	task.increasingPath(collection, 0, 2, row, col);
	task.increasingPath(collection, 0, 4, row, col);
	task.increasingPath(collection, 0, 6, row, col);
}
main();

Output

 Input Matrix
 8	 0	 1	 2	 7	 8	 10
 10	 11	 3	 1	 4	 6	 7
 21	 19	 18	 5	 14	 9	 10
 25	 20	 17	 16	 13	 12	 11


 Source point ( 0 , 0 )
 Longest Increasing Path
 8	-	-	-	-	-	-
 10	 11	-	-	-	-	-
-	 19	-	-	-	-	-
 25	 20	-	-	-	-	-

 Source point ( 1 , 3 )
 Longest Increasing Path
-	-	-	-	-	-	-
-	-	-	 1	 4	 6	-
-	 19	 18	-	-	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point ( 1 , 5 )
 Longest Increasing Path
-	-	-	-	-	-	-
-	-	-	-	-	 6	-
-	 19	 18	-	-	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point ( 0 , 2 )
 Longest Increasing Path
-	-	 1	-	-	-	-
-	-	 3	-	-	-	-
-	 19	 18	-	-	-	-
 25	 20	-	-	-	-	-

 Source point ( 0 , 4 )
 Longest Increasing Path
-	-	-	-	 7	 8	 10
-	-	-	-	-	-	-
-	-	-	-	-	-	-
-	-	-	-	-	-	-

 Source point ( 0 , 6 )
 No Increasing Path
/*
  Kotlin Program for
  Find longest increasing path in a matrix
*/
class Path
{
	var length: Int;
	constructor()
	{
		this.length = -1;
	}
	//Print grid elements
	fun printData(grid: Array<Array<Int>> , row: Int, col: Int): Unit
	{
		var i: Int = 0;
		var j: Int ;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				print(" " + grid[i][j] + "\t");
				j += 1;
			}
			print("\n");
			i += 1;
		}
		print("\n");
	}
	// Copy visitor element to output collection
	fun copyResult(collection: Array <Array<Int>> , visitor: Array <Array<Boolean>> ,
                   output: Array <Array<Int>> , row: Int, col: Int): Unit
	{
		var i: Int = 0;
		var j: Int ;
		while (i < row)
		{
			j = 0;
			while (j < col)
			{
				// Assign element
				if (visitor[i][j] == true)
				{
					output[i][j] = collection[i][j];
				}
				else
				{
					output[i][j] = 0;
				}
				j += 1;
			}
			i += 1;
		}
	}
	// Find increasing path
	// r and c is Source point
	fun findPath(collection: Array <Array<Int>> , visitor: Array<Array<Boolean>> ,
                 output: Array <Array<Int>> , r: Int, c: Int, counter: Int, row: Int, col: Int): Unit
	{
		//When not valid position
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		//When the element has been already been visited
		if (visitor[r][c] == true)
		{
			return;
		}
		//Active visiting node
		visitor[r][c] = true;
		if (this.length < counter)
		{
			// When get new increasing path
			this.length = counter;
			this.copyResult(collection, visitor, output, row, col);
		}
		// Test element in 4 direction
		if (r + 1 < row && collection[r + 1][c] > collection[r][c])
		{
			this.findPath(collection, visitor, output, r + 1, c, counter + 1, row, col);
		}
		if (c + 1 < col && collection[r][c + 1] > collection[r][c])
		{
			this.findPath(collection, visitor, output, r, c + 1, counter + 1, row, col);
		}
		if (r - 1 >= 0 && collection[r - 1][c] > collection[r][c])
		{
			this.findPath(collection, visitor, output, r - 1, c, counter + 1, row, col);
		}
		if (c - 1 >= 0 && collection[r][c - 1] > collection[r][c])
		{
			this.findPath(collection, visitor, output, r, c - 1, counter + 1, row, col);
		}
		// Deactivate visited node status
		visitor[r][c] = false;
	}
	// Handles the request to find longest increasing path
	// r and c is Source point
	fun increasingPath(collection: Array <Array<Int>> , r: Int, c: Int, row: Int, col: Int): Unit
	{
		// r and c Source point
		if (r < 0 || r >= row || c < 0 || c >= col)
		{
			return;
		}
		this.length = 0;
		//Create resultant grid
		var output: Array < Array < Int >> = Array(row)
		{
			Array(col)
			{
				0
			}
		};
		var visitor: Array < Array < Boolean >> = Array(row)
		{
			Array(col)
			{
				false
			}
		};
		this.findPath(collection, visitor, output, r, c, 0, row, col);
		print("\n Source point (" + r + "," + c + ") ");
		if (this.length != 0)
		{
			//When result are exist
			var i: Int = 0;
			var j: Int ;
			// Display solution
			print("\n Longest Increasing Path \n");
			while (i < row)
			{
				j = 0;
				while (j < col)
				{
					if (output[i][j] == 0)
					{
						print(" - \t");
					}
					else
					{
						print(" " + output[i][j] + "\t");
					}
					j += 1;
				}
				print("\n");
				i += 1;
			}
		}
		else
		{
			//When no solution possible
			print("\n No Increasing Path \n");
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Path = Path();
	var collection: Array<Array<Int>> = arrayOf(
      arrayOf(8, 0, 1, 2, 7, 8, 10), 
      arrayOf(10, 11, 3, 1, 4, 6, 7), 
      arrayOf(21, 19, 18, 5, 14, 9, 10), 
      arrayOf(25, 20, 17, 16, 13, 12, 11)
    );
	// Get size
	var row: Int = collection.count();
	var col: Int = collection[0].count();
	// Print input problem
	print("\n Input Matrix \n");
	task.printData(collection, row, col);
	// Test Cases
	task.increasingPath(collection, 0, 0, row, col);
	task.increasingPath(collection, 1, 3, row, col);
	task.increasingPath(collection, 1, 5, row, col);
	task.increasingPath(collection, 0, 2, row, col);
	task.increasingPath(collection, 0, 4, row, col);
	task.increasingPath(collection, 0, 6, row, col);
}

Output

 Input Matrix
 8	 0	 1	 2	 7	 8	 10
 10	 11	 3	 1	 4	 6	 7
 21	 19	 18	 5	 14	 9	 10
 25	 20	 17	 16	 13	 12	 11


 Source point (0,0)
 Longest Increasing Path
 8	 - 	 - 	 - 	 - 	 - 	 -
 10	 11	 - 	 - 	 - 	 - 	 -
 - 	 19	 - 	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (1,3)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 1	 4	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (1,5)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 6	 -
 - 	 19	 18	 - 	 - 	 9	 10
 25	 20	 17	 16	 13	 12	 11

 Source point (0,2)
 Longest Increasing Path
 - 	 - 	 1	 - 	 - 	 - 	 -
 - 	 - 	 3	 - 	 - 	 - 	 -
 - 	 19	 18	 - 	 - 	 - 	 -
 25	 20	 - 	 - 	 - 	 - 	 -

 Source point (0,4)
 Longest Increasing Path
 - 	 - 	 - 	 - 	 7	 8	 10
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -
 - 	 - 	 - 	 - 	 - 	 - 	 -

 Source point (0,6)
 No Increasing Path
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment