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)
{
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
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
*/
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
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 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
16
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