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 resultAlgorithm Explanation
-
maxValue(a, b)is a utility function that returns the maximum of two values. -
longestPath(matrix, track, i, j, x, y)is the main recursive function. It takes the matrix, a tracking matrixtrackto avoid revisiting cells, the current position(i, j), and the destination position(x, y). -
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.
-
If the cell is already visited or blocked, we return -1.
-
We mark the current cell as visited (
track[i][j] = 1) to avoid revisiting it. -
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.
-
We reset the tracking cell back to 0 before returning.
-
findLongestPath(matrix, x, y)initializes the tracking matrix and calculates the longest path using thelongestPathfunction. 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)
{
Path task = new Path();
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
*/
task.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
*/
task.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
*/
task.findLongestPath(matrix, 0, 2);
}
}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()
{
Path *task = new Path();
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
*/
task->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
*/
task->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
*/
task->findLongestPath(matrix, 0, 2);
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)
{
Path task = new Path();
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
*/
task.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
*/
task.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
*/
task.findLongestPath(matrix, 0, 2);
}
}Output
15
13
16package 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
*/
task.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
*/
task.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
*/
task.findLongestPath(matrix, 0, 2)
}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()
{
$task = new Path();
$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
*/
$task->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
*/
$task->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
*/
$task->findLongestPath($matrix, 0, 2);
}
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 task = new Path();
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
*/
task.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
*/
task.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
*/
task.findLongestPath(matrix, 0, 2);
}
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() :
task = Path()
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
task.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
task.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
task.findLongestPath(matrix, 0, 2)
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()
task = Path.new()
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
task.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
task.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
task.findLongestPath(matrix, 0, 2)
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
*/
task.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
*/
task.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
*/
task.findLongestPath(matrix, 0, 2);
}
}Output
15
13
16import 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 task: Path = Path();
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
*/
task.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
*/
task.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
*/
task.findLongestPath(matrix, 0, 2);
}
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 task: Path = Path();
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
*/
task.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
*/
task.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
*/
task.findLongestPath(matrix, 0, 2);
}Output
15
13
16Time 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.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment