# Find longest increasing path in a matrix

Here given code implementation process.

``````// 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)
{
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");

// Test Cases
}
}``````

#### 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()
{
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";
// Test Cases
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)
{
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");
// Test Cases
}
}``````

#### 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()
{
\$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";
// Test Cases
}
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 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");
// Test Cases
}
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() :
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 ")
#  Test Cases

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_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()
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")
#  Test Cases
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");
// Test Cases
}
}``````

#### 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 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 ");
// Test Cases
}
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 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");
// Test Cases
}``````

#### 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``````

## 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.