# Longest possible route in a matrix with hurdles

Here given code implementation process.

``````// C Program
// Longest possible route in a matrix with hurdles
#include <stdio.h>
#define N 4
#define M 5

int maxValue(int a, int b)
{
if(a > b)
{
return a;
}
else
{
return b;
}
}
int longestPath(int matrix[N][M],int track[N][M],int i, int j, int x, int y)
{

if(x >= N || y >= M || x < 0 || y < 0 ||
i < 0 || j < 0 || i >= N || j >= M)
{
// invalid position
return -1;
}

if(i == x && j==y)
{
// Reached to destination position
return 0;
}
if(track[i][j] == 1 || matrix[i][j] == 0)
{
return -1;
}
// Active track path value
track[i][j] = 1;

// visit to down row
int down = longestPath(matrix,track,i+1,j,x,y);
// visit to next col
int right = longestPath(matrix,track,i,j+1,x,y);
// visit to previous column
int left = longestPath(matrix,track,i,j-1,x,y);
// visit to up row
int up = longestPath(matrix,track,i-1,j,x,y);

// Reset value
track[i][j] = 0;

int result = maxValue(left,right);

result = maxValue(result,up);

result = maxValue(result,down);

return result + 1;

}

void findLongestPath(int matrix[N][M], int x,int y)
{

int track[N][M];

for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
track[i][j] = 0;
}
}

int result = -1;

if(x==0 && y == 0)
{
//Source and destination are same point
result = 0;
}
else
{
result = longestPath(matrix,track,0,0,x,y);
}

if(result==-1)
{
printf("\n No path");
}
else
{
printf("\n %d",result);
}
}

int main()
{

int matrix[N][M] =
{
{ 1, 1, 1, 1, 1 },
{ 1, 1, 0, 1, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1 }
};
/*
Source [0][0]
Destination [2][1]
--------------------
1 → 1 → 1 → 1   1
↓
1 → 1   0   1   0
↑   ↓       ↓
1   1   1   1 → 1
↑               ↓
1 ← 1 ← 1 ← 1 ← 1
-----------------
Result = 15
Note that there is more than one solution possible
*/

findLongestPath(matrix,2,1);
/*
Source [0][0]
Destination [2][3]
--------------------
1 → 1   1   1   1
↓
1 ← 1   0   1   0
↓
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 13
*/
findLongestPath(matrix,2,3);

/*
Source [0][0]
Destination [0][2]
--------------------
1 → 1   1 ← 1   1
↓       ↑
1 ← 1   0   1   0
↓           ↑
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 16
*/
findLongestPath(matrix,0,2);
return 0;
}``````

#### Output

`````` 15
13
16``````
``````/*
Java Program for
Longest possible route in a matrix with hurdles
*/

public class Path
{

public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
public int longestPath(int[][] matrix, boolean[][] track,
int i, int j, int x, int y, int n, int m)
{
if (x >= n || y >= m || x < 0 || y < 0 || i < 0 ||
j < 0 || i >= n || j >= m)
{
// invalid position
return -1;
}
if (i == x && j == y)
{
// Reached to destination position
return 0;
}
if (track[i][j] == true || matrix[i][j] == 0)
{
return -1;
}
// Active track path value
track[i][j] = true;
// visit to down row
int down = longestPath(matrix, track, i + 1, j, x, y, n,m);
// visit to next column
int right = longestPath(matrix, track, i, j + 1, x, y, n,m);
// visit to previous column
int left = longestPath(matrix, track, i, j - 1, x, y, n,m);
// visit to up row
int up = longestPath(matrix, track, i - 1, j, x, y, n,m);
// Reset value
track[i][j] = false;
int result = maxValue(left, right);
result = maxValue(result, up);
result = maxValue(result, down);
return result + 1;
}
public void findLongestPath(int[][] matrix, int x, int y)
{
int n = matrix.length;
int m = matrix[0].length;
boolean[][] track = new boolean[n][m];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
track[i][j] = false;
}
}
int result = -1;
if (x == 0 && y == 0)
{
//Source and destination are same point
result = 0;
}
else
{
result = longestPath(matrix, track, 0, 0, x, y, n, m);
}
if (result == -1)
{
System.out.print("\n No path");
}
else
{
System.out.print("\n " + result );
}
}
public static void main(String[] args)
{

int[][] matrix  =
{
{
1 , 1 , 1 , 1 , 1
} ,
{
1 , 1 , 0 , 1 , 0
} ,
{
1 , 1 , 1 , 1 , 1
} ,
{
1 , 1 , 1 , 1 , 1
}
};
/*
Source [0][0]
Destination [2][1]
--------------------
1 → 1 → 1 → 1   1
↓
1 → 1   0   1   0
↑   ↓       ↓
1   1   1   1 → 1
↑               ↓
1 ← 1 ← 1 ← 1 ← 1
-----------------
Result = 15
--------------------
Note that there is more than one solution possible
*/

/*
Source [0][0]
Destination [2][3]
--------------------
1 → 1   1   1   1
↓
1 ← 1   0   1   0
↓
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 13
*/
/*
Source [0][0]
Destination [0][2]
--------------------
1 → 1   1 ← 1   1
↓       ↑
1 ← 1   0   1   0
↓           ↑
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 16
*/

}
}``````

#### Output

`````` 15
13
16``````
``````// Include header file
#include <iostream>
#define N 4
#define M 5
using namespace std;
/*
C++ Program for
Longest possible route in a matrix with hurdles
*/
class Path
{
public: int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
int longestPath(int matrix[N][M], bool track[N][M],
int i, int j, int x, int y)
{
if (x >= N || y >= M || x < 0 || y < 0 ||
i < 0 || j < 0 || i >= N || j >= M)
{
// invalid position
return -1;
}
if (i == x && j == y)
{
// Reached to destination position
return 0;
}
if (track[i][j] == true || matrix[i][j] == 0)
{
return -1;
}
// Active track path value
track[i][j] = true;
// visit to down row
int down = this->longestPath(matrix, track, i + 1, j, x, y);
// visit to next column
int right = this->longestPath(matrix, track, i, j + 1, x, y);
// visit to previous column
int left = this->longestPath(matrix, track, i, j - 1, x, y);
// visit to up row
int up = this->longestPath(matrix, track, i - 1, j, x, y);
// Reset value
track[i][j] = false;
int result = this->maxValue(left, right);
result = this->maxValue(result, up);
result = this->maxValue(result, down);
return result + 1;
}
void findLongestPath(int matrix[N][M], int x, int y)
{

bool track[N][M];
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
track[i][j] = false;
}
}
int result = -1;
if (x == 0 && y == 0)
{
//Source and destination are same point
result = 0;
}
else
{
result = this->longestPath(matrix, track, 0, 0, x, y);
}
if (result == -1)
{
cout << "\n No path";
}
else
{
cout << "\n " << result;
}
}
};
int main()
{
int matrix[N][M] = {
{
1 , 1 , 1 , 1 , 1
} , {
1 , 1 , 0 , 1 , 0
} , {
1 , 1 , 1 , 1 , 1
} , {
1 , 1 , 1 , 1 , 1
}
};
/*
Source [0][0]
Destination [2][1]
--------------------
1 → 1 → 1 → 1   1
↓
1 → 1   0   1   0
↑   ↓       ↓
1   1   1   1 → 1
↑               ↓
1 ← 1 ← 1 ← 1 ← 1
-----------------
Result = 15
--------------------
Note that there is more than one solution possible
*/
/*
Source [0][0]
Destination [2][3]
--------------------
1 → 1   1   1   1
↓
1 ← 1   0   1   0
↓
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 13
*/
/*
Source [0][0]
Destination [0][2]
--------------------
1 → 1   1 ← 1   1
↓       ↑
1 ← 1   0   1   0
↓           ↑
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 16
*/
return 0;
}``````

#### Output

`````` 15
13
16``````
``````// Include namespace system
using System;
/*
Csharp Program for
Longest possible route in a matrix with hurdles
*/
public class Path
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
public int longestPath(int[,] matrix, Boolean[,] track,
int i, int j, int x, int y, int n, int m)
{
if (x >= n || y >= m || x < 0 || y < 0 ||
i < 0 || j < 0 || i >= n || j >= m)
{
// invalid position
return -1;
}
if (i == x && j == y)
{
// Reached to destination position
return 0;
}
if (track[i,j] == true || matrix[i,j] == 0)
{
return -1;
}
// Active track path value
track[i,j] = true;
// visit to down row
int down = this.longestPath(matrix, track, i + 1, j, x, y, n, m);
// visit to next column
int right = this.longestPath(matrix, track, i, j + 1, x, y, n, m);
// visit to previous column
int left = this.longestPath(matrix, track, i, j - 1, x, y, n, m);
// visit to up row
int up = this.longestPath(matrix, track, i - 1, j, x, y, n, m);
// Reset value
track[i,j] = false;
int result = this.maxValue(left, right);
result = this.maxValue(result, up);
result = this.maxValue(result, down);
return result + 1;
}
public void findLongestPath(int[,] matrix, int x, int y)
{
int n = matrix.GetLength(0);
int m = matrix.GetLength(1);
Boolean[,] track = new Boolean[n,m];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
track[i,j] = false;
}
}
int result = -1;
if (x == 0 && y == 0)
{
//Source and destination are same point
result = 0;
}
else
{
result = this.longestPath(matrix, track, 0, 0, x, y, n, m);
}
if (result == -1)
{
Console.Write("\n No path");
}
else
{
Console.Write("\n " + result);
}
}
public static void Main(String[] args)
{
int[,] matrix = {
{
1 , 1 , 1 , 1 , 1
},
{
1 , 1 , 0 , 1 , 0
},
{
1 , 1 , 1 , 1 , 1
},
{
1 , 1 , 1 , 1 , 1
}
};
/*
Source [0,0]
Destination [2,1]
--------------------
1 → 1 → 1 → 1   1
↓
1 → 1   0   1   0
↑   ↓       ↓
1   1   1   1 → 1
↑               ↓
1 ← 1 ← 1 ← 1 ← 1
-----------------
Result = 15
--------------------
Note that there is more than one solution possible
*/
/*
Source [0,0]
Destination [2,3]
--------------------
1 → 1   1   1   1
↓
1 ← 1   0   1   0
↓
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 13
*/
/*
Source [0,0]
Destination [0,2]
--------------------
1 → 1   1 ← 1   1
↓       ↑
1 ← 1   0   1   0
↓           ↑
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 16
*/
}
}``````

#### Output

`````` 15
13
16``````
``````package main
import "fmt"
/*
Go Program for
Longest possible route in a matrix with hurdles
*/
type Path struct {}
func getPath() * Path {
var me *Path = &Path {}
return me
}
func(this Path) maxValue(a, b int) int {
if a > b {
return a
} else {
return b
}
}
func(this Path) longestPath(matrix[][] int, track[][] bool,
i int, j int, x int, y int, n int, m int) int {
if x >= n || y >= m ||
x < 0 || y < 0 || i < 0 || j < 0 || i >= n || j >= m {
// invalid position
return -1
}
if i == x && j == y {
// Reached to destination position
return 0
}
if track[i][j] == true || matrix[i][j] == 0 {
return -1
}
// Active track path value
track[i][j] = true
// visit to down row
var down int = this.longestPath(matrix, track, i + 1, j, x, y, n, m)
// visit to next column
var right int = this.longestPath(matrix, track, i, j + 1, x, y, n, m)
// visit to previous column
var left int = this.longestPath(matrix, track, i, j - 1, x, y, n, m)
// visit to up row
var up int = this.longestPath(matrix, track, i - 1, j, x, y, n, m)
// Reset value
track[i][j] = false
var result int = this.maxValue(left, right)
result = this.maxValue(result, up)
result = this.maxValue(result, down)
return result + 1
}
func(this Path) findLongestPath(matrix[][] int, x int, y int) {
var n int = len(matrix)
var m int = len(matrix[0])
var track = make([][] bool, n)
for i:= 0;i < n;i++ {
track[i] = make([]bool,m)
}
var result int = -1
if x == 0 && y == 0 {
//Source and destination are same point
result = 0
} else {
result = this.longestPath(matrix, track, 0, 0, x, y, n, m)
}
if result == -1 {
fmt.Print("\n No path")
} else {
fmt.Print("\n ", result)
}
}
func main() {
var task * Path = getPath()
var matrix = [][] int {{ 1, 1, 1, 1, 1 },
{ 1, 1, 0, 1, 0 },
{ 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1 }}
/*
Source [0][0]
Destination [2][1]
--------------------
1 → 1 → 1 → 1   1
↓
1 → 1   0   1   0
↑   ↓       ↓
1   1   1   1 → 1
↑               ↓
1 ← 1 ← 1 ← 1 ← 1
-----------------
Result = 15
--------------------
Note that there is more than one solution possible
*/
/*
Source [0][0]
Destination [2][3]
--------------------
1 → 1   1   1   1
↓
1 ← 1   0   1   0
↓
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 13
*/
/*
Source [0][0]
Destination [0][2]
--------------------
1 → 1   1 ← 1   1
↓       ↑
1 ← 1   0   1   0
↓           ↑
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 16
*/
}``````

#### Output

`````` 15
13
16``````
``````<?php
/*
Php Program for
Longest possible route in a matrix with hurdles
*/
class Path
{
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
else
{
return \$b;
}
}
public	function longestPath(\$matrix, &\$track, \$i, \$j, \$x, \$y, \$n, \$m)
{
if (\$x >= \$n || \$y >= \$m || \$x < 0 || \$y < 0 ||
\$i < 0 || \$j < 0 || \$i >= \$n || \$j >= \$m)
{
// invalid position
return -1;
}
if (\$i == \$x && \$j == \$y)
{
// Reached to destination position
return 0;
}
if (\$track[\$i][\$j] == true || \$matrix[\$i][\$j] == 0)
{
return -1;
}
// Active track path value
\$track[\$i][\$j] = true;
// visit to down row
\$down = \$this->longestPath(\$matrix, \$track, \$i + 1, \$j, \$x, \$y, \$n, \$m);
// visit to next column
\$right = \$this->longestPath(\$matrix, \$track, \$i, \$j + 1, \$x, \$y, \$n, \$m);
// visit to previous column
\$left = \$this->longestPath(\$matrix, \$track, \$i, \$j - 1, \$x, \$y, \$n, \$m);
// visit to up row
\$up = \$this->longestPath(\$matrix, \$track, \$i - 1, \$j, \$x, \$y, \$n, \$m);
// Reset value
\$track[\$i][\$j] = false;
\$result = \$this->maxValue(\$left, \$right);
\$result = \$this->maxValue(\$result, \$up);
\$result = \$this->maxValue(\$result, \$down);
return \$result + 1;
}
public	function findLongestPath(\$matrix, \$x, \$y)
{
\$n = count(\$matrix);
\$m = count(\$matrix[0]);
\$track = array_fill(0, \$n, array_fill(0, \$m, false));
\$result = -1;
if (\$x == 0 && \$y == 0)
{
//Source and destination are same point
\$result = 0;
}
else
{
\$result = \$this->longestPath(\$matrix, \$track, 0, 0, \$x, \$y, \$n, \$m);
}
if (\$result == -1)
{
echo("\n No path");
}
else
{
echo("\n ".\$result);
}
}
}

function main()
{
\$matrix = array(
array(1, 1, 1, 1, 1),
array(1, 1, 0, 1, 0),
array(1, 1, 1, 1, 1),
array(1, 1, 1, 1, 1)
);
/*
Source [0][0]
Destination [2][1]
--------------------
1 → 1 → 1 → 1   1
↓
1 → 1   0   1   0
↑   ↓       ↓
1   1   1   1 → 1
↑               ↓
1 ← 1 ← 1 ← 1 ← 1
-----------------
Result = 15
--------------------
Note that there is more than one solution possible
*/
/*
Source [0][0]
Destination [2][3]
--------------------
1 → 1   1   1   1
↓
1 ← 1   0   1   0
↓
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 13
*/
/*
Source [0][0]
Destination [0][2]
--------------------
1 → 1   1 ← 1   1
↓       ↑
1 ← 1   0   1   0
↓           ↑
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 16
*/
}
main();``````

#### Output

`````` 15
13
16``````
``````/*
Node JS Program for
Longest possible route in a matrix with hurdles
*/
class Path
{
maxValue(a, b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
longestPath(matrix, track, i, j, x, y, n, m)
{
if (x >= n || y >= m || x < 0 || y < 0 ||
i < 0 || j < 0 || i >= n || j >= m)
{
// invalid position
return -1;
}
if (i == x && j == y)
{
// Reached to destination position
return 0;
}
if (track[i][j] == true || matrix[i][j] == 0)
{
return -1;
}
// Active track path value
track[i][j] = true;
// visit to down row
var down = this.longestPath(matrix, track, i + 1, j, x, y, n, m);
// visit to next column
var right = this.longestPath(matrix, track, i, j + 1, x, y, n, m);
// visit to previous column
var left = this.longestPath(matrix, track, i, j - 1, x, y, n, m);
// visit to up row
var up = this.longestPath(matrix, track, i - 1, j, x, y, n, m);
// Reset value
track[i][j] = false;
var result = this.maxValue(left, right);
result = this.maxValue(result, up);
result = this.maxValue(result, down);
return result + 1;
}
findLongestPath(matrix, x, y)
{
var n = matrix.length;
var m = matrix[0].length;
var track = Array(n).fill(false).map(() => new Array(m).fill(false));
var result = -1;
if (x == 0 && y == 0)
{
//Source and destination are same point
result = 0;
}
else
{
result = this.longestPath(matrix, track, 0, 0, x, y, n, m);
}
if (result == -1)
{
process.stdout.write("\n No path");
}
else
{
process.stdout.write("\n " + result);
}
}
}

function main()
{
var matrix = [
[1, 1, 1, 1, 1],
[1, 1, 0, 1, 0],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1]
];
/*
Source [0][0]
Destination [2][1]
--------------------
1 → 1 → 1 → 1   1
↓
1 → 1   0   1   0
↑   ↓       ↓
1   1   1   1 → 1
↑               ↓
1 ← 1 ← 1 ← 1 ← 1
-----------------
Result = 15
--------------------
Note that there is more than one solution possible
*/
/*
Source [0][0]
Destination [2][3]
--------------------
1 → 1   1   1   1
↓
1 ← 1   0   1   0
↓
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 13
*/
/*
Source [0][0]
Destination [0][2]
--------------------
1 → 1   1 ← 1   1
↓       ↑
1 ← 1   0   1   0
↓           ↑
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 16
*/
}
main();``````

#### Output

`````` 15
13
16``````
``````#    Python 3 Program for
#    Longest possible route in a matrix with hurdles
class Path :
def maxValue(self, a, b) :
if (a > b) :
return a
else :
return b

def longestPath(self, matrix, track, i, j, x, y, n, m) :
if (x >= n or y >= m or x < 0 or y < 0 or
i < 0 or j < 0 or i >= n or j >= m) :
#  invalid position
return -1

if (i == x and j == y) :
#  Reached to destination position
return 0

if (track[i][j] == True or matrix[i][j] == 0) :
return -1

#  Active track path value
track[i][j] = True
#  visit to down row
down = self.longestPath(matrix, track, i + 1, j, x, y, n, m)
#  visit to next column
right = self.longestPath(matrix, track, i, j + 1, x, y, n, m)
#  visit to previous column
left = self.longestPath(matrix, track, i, j - 1, x, y, n, m)
#  visit to up row
up = self.longestPath(matrix, track, i - 1, j, x, y, n, m)
#  Reset value
track[i][j] = False
result = self.maxValue(left, right)
result = self.maxValue(result, up)
result = self.maxValue(result, down)
return result + 1

def findLongestPath(self, matrix, x, y) :
n = len(matrix)
m = len(matrix[0])
track = [[False] * (m) for _ in range(n) ]
result = -1
if (x == 0 and y == 0) :
# Source and destination are same point
result = 0
else :
result = self.longestPath(matrix, track, 0, 0, x, y, n, m)

if (result == -1) :
print("\n No path", end = "")
else :
print("\n ", result, end = "")

def main() :
matrix = [
[1, 1, 1, 1, 1],
[1, 1, 0, 1, 0],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1]
]
#    Source [0][0]
#    Destination [2][1]
#    --------------------
#    1 → 1 → 1 → 1   1
#                ↓
#    1 → 1   0   1   0
#    ↑   ↓       ↓
#    1   1   1   1 → 1
#    ↑               ↓
#    1 ← 1 ← 1 ← 1 ← 1
#    -----------------
#    Result = 15
#    --------------------
#    Note that there is more than one solution possible
#    Source [0][0]
#    Destination [2][3]
#    --------------------
#    1 → 1   1   1   1
#        ↓
#    1 ← 1   0   1   0
#    ↓
#    1   1 → 1   1 ← 1
#    ↓   ↑   ↓       ↑
#    1 → 1   1 → 1 → 1
#    -----------------
#    Result = 13
#    Source [0][0]
#    Destination [0][2]
#    --------------------
#    1 → 1   1 ← 1   1
#        ↓       ↑
#    1 ← 1   0   1   0
#    ↓           ↑
#    1   1 → 1   1 ← 1
#    ↓   ↑   ↓       ↑
#    1 → 1   1 → 1 → 1
#    -----------------
#    Result = 16

if __name__ == "__main__": main()``````

#### Output

``````  15
13
16``````
``````#    Ruby Program for
#    Longest possible route in a matrix with hurdles
class Path
def maxValue(a, b)
if (a > b)
return a
else

return b
end

end

def longestPath(matrix, track, i, j, x, y, n, m)
if (x >= n || y >= m || x < 0 || y < 0 || i < 0 ||
j < 0 || i >= n || j >= m)
#  invalid position
return -1
end

if (i == x && j == y)
#  Reached to destination position
return 0
end

if (track[i][j] == true || matrix[i][j] == 0)
return -1
end

#  Active track path value
track[i][j] = true
#  visit to down row
down = self.longestPath(matrix, track, i + 1, j, x, y, n, m)
#  visit to next column
right = self.longestPath(matrix, track, i, j + 1, x, y, n, m)
#  visit to previous column
left = self.longestPath(matrix, track, i, j - 1, x, y, n, m)
#  visit to up row
up = self.longestPath(matrix, track, i - 1, j, x, y, n, m)
#  Reset value
track[i][j] = false
result = self.maxValue(left, right)
result = self.maxValue(result, up)
result = self.maxValue(result, down)
return result + 1
end

def findLongestPath(matrix, x, y)
n = matrix.length
m = matrix[0].length
track = Array.new(n) {Array.new(m) {false}}
result = -1
if (x == 0 && y == 0)
# Source and destination are same point
result = 0
else

result = self.longestPath(matrix, track, 0, 0, x, y, n, m)
end

if (result == -1)
print("\n No path")
else

print("\n ", result)
end

end

end

def main()
matrix = [
[1, 1, 1, 1, 1],
[1, 1, 0, 1, 0],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1]
]
#    Source [0][0]
#    Destination [2][1]
#    --------------------
#    1 → 1 → 1 → 1   1
#                ↓
#    1 → 1   0   1   0
#    ↑   ↓       ↓
#    1   1   1   1 → 1
#    ↑               ↓
#    1 ← 1 ← 1 ← 1 ← 1
#    -----------------
#    Result = 15
#    --------------------
#    Note that there is more than one solution possible
#    Source [0][0]
#    Destination [2][3]
#    --------------------
#    1 → 1   1   1   1
#        ↓
#    1 ← 1   0   1   0
#    ↓
#    1   1 → 1   1 ← 1
#    ↓   ↑   ↓       ↑
#    1 → 1   1 → 1 → 1
#    -----------------
#    Result = 13
#    Source [0][0]
#    Destination [0][2]
#    --------------------
#    1 → 1   1 ← 1   1
#        ↓       ↑
#    1 ← 1   0   1   0
#    ↓           ↑
#    1   1 → 1   1 ← 1
#    ↓   ↑   ↓       ↑
#    1 → 1   1 → 1 → 1
#    -----------------
#    Result = 16
end

main()``````

#### Output

`````` 15
13
16``````
``````/*
Scala Program for
Longest possible route in a matrix with hurdles
*/
class Path()
{
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
else
{
return b;
}
}
def longestPath(
matrix: Array[Array[Int]],
track: Array[Array[Boolean]],
i: Int, j: Int, x: Int, y: Int,
n: Int, m: Int): Int = {
if (x >= n || y >= m || x < 0 || y < 0 ||
i < 0 || j < 0 || i >= n || j >= m)
{
// invalid position
return -1;
}
if (i == x && j == y)
{
// Reached to destination position
return 0;
}
if (track(i)(j) == true || matrix(i)(j) == 0)
{
return -1;
}
// Active track path value
track(i)(j) = true;
// visit to down row
var down: Int = longestPath(matrix, track, i + 1, j, x, y, n, m);
// visit to next column
var right: Int = longestPath(matrix, track, i, j + 1, x, y, n, m);
// visit to previous column
var left: Int = longestPath(matrix, track, i, j - 1, x, y, n, m);
// visit to up row
var up: Int = longestPath(matrix, track, i - 1, j, x, y, n, m);
// Reset value
track(i)(j) = false;
var result: Int = maxValue(left, right);
result = maxValue(result, up);
result = maxValue(result, down);
return result + 1;
}
def findLongestPath(matrix: Array[Array[Int]], x: Int, y: Int): Unit = {
var n: Int = matrix.length;
var m: Int = matrix(0).length;
var track: Array[Array[Boolean]] = Array.fill[Boolean](n, m)(false);
var result: Int = -1;
if (x == 0 && y == 0)
{
//Source and destination are same point
result = 0;
}
else
{
result = longestPath(matrix, track, 0, 0, x, y, n, m);
}
if (result == -1)
{
print("\n No path");
}
else
{
print("\n " + result);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Path = new Path();
var matrix: Array[Array[Int]] = Array(
Array(1, 1, 1, 1, 1),
Array(1, 1, 0, 1, 0),
Array(1, 1, 1, 1, 1),
Array(1, 1, 1, 1, 1)
);
/*
Source [0][0]
Destination [2][1]
--------------------
1 → 1 → 1 → 1   1
↓
1 → 1   0   1   0
↑   ↓       ↓
1   1   1   1 → 1
↑               ↓
1 ← 1 ← 1 ← 1 ← 1
-----------------
Result = 15
--------------------
Note that there is more than one solution possible
*/
/*
Source [0][0]
Destination [2][3]
--------------------
1 → 1   1   1   1
↓
1 ← 1   0   1   0
↓
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 13
*/
/*
Source [0][0]
Destination [0][2]
--------------------
1 → 1   1 ← 1   1
↓       ↑
1 ← 1   0   1   0
↓           ↑
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 16
*/
}
}``````

#### Output

`````` 15
13
16``````
``````import Foundation;
/*
Swift 4 Program for
Longest possible route in a matrix with hurdles
*/
class Path
{
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
func longestPath(_ matrix: [[Int]], _ track: inout[[Bool]],
_ i: Int, _ j: Int, _ x: Int, _ y: Int, _ n: Int, _ m: Int) -> Int
{
if (x >= n || y >= m || x < 0 || y < 0 ||
i < 0 || j < 0 || i >= n || j >= m)
{
// invalid position
return -1;
}
if (i == x && j == y)
{
// Reached to destination position
return 0;
}
if (track[i][j] == true || matrix[i][j] == 0)
{
return -1;
}
// Active track path value
track[i][j] = true;
// visit to down row
let down: Int =
self.longestPath(matrix, &track, i + 1, j, x, y, n, m);
// visit to next column
let right: Int =
self.longestPath(matrix, &track, i, j + 1, x, y, n, m);
// visit to previous column
let left: Int =
self.longestPath(matrix, &track, i, j - 1, x, y, n, m);
// visit to up row
let up: Int =
self.longestPath(matrix, &track, i - 1, j, x, y, n, m);
// Reset value
track[i][j] = false;
var result: Int = self.maxValue(left, right);
result = self.maxValue(result, up);
result = self.maxValue(result, down);
return result + 1;
}
func findLongestPath(_ matrix: [[Int]], _ x: Int, _ y: Int)
{
let n: Int = matrix.count;
let m: Int = matrix[0].count;
var track: [
[Bool]
] = Array(repeating: Array(repeating: false, count: m), count: n);
var result: Int = -1;
if (x == 0 && y == 0)
{
//Source and destination are same point
result = 0;
}
else
{
result = self.longestPath(matrix, &track, 0, 0, x, y, n, m);
}
if (result == -1)
{
print("\n No path", terminator: "");
}
else
{
print("\n ", result, terminator: "");
}
}
}
func main()
{
let matrix: [
[Int]
] = [
[1, 1, 1, 1, 1],
[1, 1, 0, 1, 0],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1]
];
/*
Source [0][0]
Destination [2][1]
--------------------
1 → 1 → 1 → 1   1
↓
1 → 1   0   1   0
↑   ↓       ↓
1   1   1   1 → 1
↑               ↓
1 ← 1 ← 1 ← 1 ← 1
-----------------
Result = 15
--------------------
Note that there is more than one solution possible
*/
/*
Source [0][0]
Destination [2][3]
--------------------
1 → 1   1   1   1
↓
1 ← 1   0   1   0
↓
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 13
*/
/*
Source [0][0]
Destination [0][2]
--------------------
1 → 1   1 ← 1   1
↓       ↑
1 ← 1   0   1   0
↓           ↑
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 16
*/
}
main();``````

#### Output

``````  15
13
16``````
``````/*
Kotlin Program for
Longest possible route in a matrix with hurdles
*/
class Path
{
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
fun longestPath(matrix: Array < Array < Int >> ,
track: Array < Array < Boolean >> ,
i: Int, j: Int, x: Int, y: Int, n: Int, m: Int): Int
{
if (x >= n || y >= m || x < 0 || y < 0 || i < 0 ||
j < 0 || i >= n || j >= m)
{
// invalid position
return -1;
}
if (i == x && j == y)
{
// Reached to destination position
return 0;
}
if (track[i][j] == true || matrix[i][j] == 0)
{
return -1;
}
// Active track path value
track[i][j] = true;
// visit to down row
val down: Int = this.longestPath(matrix, track, i + 1, j, x, y, n, m);
// visit to next column
val right: Int = this.longestPath(matrix, track, i, j + 1, x, y, n, m);
// visit to previous column
val left: Int = this.longestPath(matrix, track, i, j - 1, x, y, n, m);
// visit to up row
val up: Int = this.longestPath(matrix, track, i - 1, j, x, y, n, m);
// Reset value
track[i][j] = false;
var result: Int = this.maxValue(left, right);
result = this.maxValue(result, up);
result = this.maxValue(result, down);
return result + 1;
}
fun findLongestPath(matrix: Array < Array < Int >> , x: Int, y: Int): Unit
{
val n: Int = matrix.count();
val m: Int = matrix[0].count();
val track: Array < Array < Boolean >> = Array(n)
{
Array(m)
{
false
}
};
var result: Int ;
if (x == 0 && y == 0)
{
//Source and destination are same point
result = 0;
}
else
{
result = this.longestPath(matrix, track, 0, 0, x, y, n, m);
}
if (result == -1)
{
print("\n No path");
}
else
{
print("\n " + result);
}
}
}
fun main(args: Array < String > ): Unit
{
val matrix: Array < Array < Int >> = arrayOf(
arrayOf(1, 1, 1, 1, 1),
arrayOf(1, 1, 0, 1, 0),
arrayOf(1, 1, 1, 1, 1),
arrayOf(1, 1, 1, 1, 1)
);
/*
Source [0][0]
Destination [2][1]
--------------------
1 → 1 → 1 → 1   1
↓
1 → 1   0   1   0
↑   ↓       ↓
1   1   1   1 → 1
↑               ↓
1 ← 1 ← 1 ← 1 ← 1
-----------------
Result = 15
--------------------
Note that there is more than one solution possible
*/
/*
Source [0][0]
Destination [2][3]
--------------------
1 → 1   1   1   1
↓
1 ← 1   0   1   0
↓
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 13
*/
/*
Source [0][0]
Destination [0][2]
--------------------
1 → 1   1 ← 1   1
↓       ↑
1 ← 1   0   1   0
↓           ↑
1   1 → 1   1 ← 1
↓   ↑   ↓       ↑
1 → 1   1 → 1 → 1
-----------------
Result = 16
*/
}``````

#### Output

`````` 15
13
16``````

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