# Longest possible route in a matrix with hurdles

Finding the longest possible route in a matrix from a given source cell to a destination cell, while considering the presence of hurdles in the matrix. The goal is to determine the maximum number of steps one can take while moving only in up, down, left, or right directions, and avoiding the hurdles.

## Problem Statement and Description

Given a matrix representing a grid with cells and hurdles, we want to find the longest possible route from a specified source cell to a destination cell. Each cell can be either open (denoted by '1') or blocked by a hurdle (denoted by '0'). Movement is allowed only to adjacent open cells (up, down, left, or right), and the goal is to find the maximum number of steps taken to reach the destination while avoiding hurdles.

## Idea to Solve the Problem

To solve this problem, we can use a depth-first search (DFS) approach with backtracking. We start from the source cell, explore all possible paths by moving in the allowed directions, and keep track of the maximum length achieved. We also need to ensure that we don't visit the same cell multiple times and avoid moving to cells blocked by hurdles.

## Pseudocode

``````maxValue(a, b):
if a > b:
return a
else:
return b

longestPath(matrix, track, i, j, x, y):
if invalid position (i.e., out of bounds or blocked):
return -1
if reached destination (i == x and j == y):
return 0
if track[i][j] == 1 or matrix[i][j] == 0:
return -1
track[i][j] = 1
down = longestPath(matrix, track, i + 1, j, x, y)
right = longestPath(matrix, track, i, j + 1, x, y)
left = longestPath(matrix, track, i, j - 1, x, y)
up = longestPath(matrix, track, i - 1, j, x, y)
track[i][j] = 0
result = maxValue(left, right)
result = maxValue(result, up)
result = maxValue(result, down)
return result + 1

findLongestPath(matrix, x, y):
initialize track matrix with all zeros
result = -1
if source is the same as destination:
result = 0
else:
result = longestPath(matrix, track, 0, 0, x, y)
if result == -1:
print "No path"
else:
print result``````

## Algorithm Explanation

1. `maxValue(a, b)` is a utility function that returns the maximum of two values.

2. `longestPath(matrix, track, i, j, x, y)` is the main recursive function. It takes the matrix, a tracking matrix `track` to avoid revisiting cells, the current position `(i, j)`, and the destination position `(x, y)`.

3. We check for invalid positions (out of bounds or blocked cells), and if the current cell is the destination, we return 0 as we've reached the destination.

4. If the cell is already visited or blocked, we return -1.

5. We mark the current cell as visited (`track[i][j] = 1`) to avoid revisiting it.

6. We recursively explore all four possible directions (up, down, left, right) and calculate the longest path length by taking the maximum of the lengths from each direction.

7. We reset the tracking cell back to 0 before returning.

8. `findLongestPath(matrix, x, y)` initializes the tracking matrix and calculates the longest path using the `longestPath` function. If no path is found, it prints "No path."

## Code Solution

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

## Time Complexity

The time complexity of this algorithm depends on the number of recursive calls made and the size of the matrix. In the worst case, where there are no hurdles and the path explores all possible directions, the time complexity can be exponential. The complexity is O(4^(N*M)), where N is the number of rows and M is the number of columns in the matrix. However, with the presence of hurdles, the actual time complexity will be lower due to backtracking.

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