Given an MxN matrix, with a few hurdles arbitrarily placed, calculate the cost of longest possible route from point A to point B within the matrix.
Input Format:
1. First line contains 2 numbers delimited by whitespace where, first number M is number of rows and second number N is number of columns.
2. Second line contains number of hurdles H followed by H lines, each line will contain one hurdle point in the matrix.
3. Next line will contain point A, starting point in the matrix.
4. Next line will contain point B, stop point in the matrix.
Output Format:
Output should display the length of the longest route from point A to point B in the matrix.
Constraints:
1. The cost from one position to another will be 1 unit.
2. A location once visited in a particular path cannot be visited again.
3. A route will only consider adjacent hops. The route cannot consist of diagonal hops.
4. The position with a hurdle cannot be visited.
5. The values MxN signifies that the matrix consists of rows ranging from 0 to M-1 and columns ranging from 0 to N-1.
6. If the destination is not reachable or source/ destination overlap with hurdles, print cost as -1.
Input:
1 0 1 1 1 1 0 1 1 1
1 0 1 0 1 1 1 0 1 1
1 1 1 0 1 1 0 1 0 1
0 0 0 0 1 0 0 1 0 0
1 0 0 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 0 0 0 1 0 0 1 0 1
1 0 1 1 1 1 0 0 1 1
1 1 0 0 1 0 0 0 0 1
1 0 1 1 1 1 0 1 0 0
0 0
5 7
Output:
24
Explanation:
Here matrix will be of size 3×10 matrix with a hurdle at (1,2),(1,5 ) and (1,8) with starting point A(0,0) and stop point B(1,7)
3 10
3 — (no. of hurdles )
1 2
1 5
1 8
0 0 — (position of A)
1 7 — (position of B)
So if you examine matrix below shown in Fig 1, total hops ( ->) count is 24. So final answer will be 24. No other route longer than this one is possible in this matrix.
Solution: In C
#include <stdio.h>
#include<math.h>
#include <stdlib.h>
#include<string.h>
#define M 10
#define N 10
bool isSafe(int mat[M][N], int visited[M][N], int x, int y)
{
if (mat[x][y] == 0 || visited[x][y])
return false;
return true;
}
bool isValid(int x, int y)
{
if (x < M && y < N && x >= 0 && y >= 0)
return true;
return false;
}
void findLongestPath(int mat[M][N], int visited[M][N], int i, int j, int x, int y, int& max_dist, int dist)
{
if (mat[i][j] == 0)
return;
if (i == x && j == y)
{
max_dist = dist > max_dist ? dist : max_dist;
return;
}
visited[i][j] = 1;
if (isValid(i + 1, j) && isSafe(mat, visited, i + 1, j))
findLongestPath(mat, visited, i + 1, j, x, y, max_dist, dist + 1);
if (isValid(i, j + 1) && isSafe(mat, visited, i, j + 1))
findLongestPath(mat, visited, i, j + 1, x, y, max_dist, dist + 1);
if (isValid(i - 1, j) && isSafe(mat, visited, i - 1, j))
findLongestPath(mat, visited, i - 1, j, x, y, max_dist, dist + 1);
if (isValid(i, j - 1) && isSafe(mat, visited, i, j - 1))
findLongestPath(mat, visited, i, j - 1, x, y, max_dist, dist + 1);
visited[i][j] = 0;
}
int main()
{
int mat[M][N];
for(int i=0;i<M;i++)
for(int j=0;j<N;j++)
scanf("%d",&mat[i][j]);
int a,b,c,d;
scanf("%d %d",&a,&b);
scanf("%d %d",&c,&d);
int visited[M][N];
memset(visited, 0, sizeof visited);
int max_dist = 0;
findLongestPath(mat, visited, a, b, c, d, max_dist, 0);
printf("%d",max_dist);
return 0;
}Solution: In Java
import java.util.*;
class Main
{
private static final int M = 10;
private static final int N = 10;
private static boolean isSafe(int mat[][], int visited[][], int x, int y)
{
if (mat[x][y] == 0 || visited[x][y] != 0)
return false;
return true;
}
private static boolean isValid(int x, int y)
{
if (x < M && y < N && x >= 0 && y >= 0)
return true;
return false;
}
public static int findLongestPath(int mat[][], int visited[][], int i, int j, int x, int y, int max_dist, int dist)
{
if (mat[i][j] == 0) {
return 0;
}
if (i == x && j == y)
{
return Integer.max(dist, max_dist);
}
visited[i][j] = 1;
if (isValid(i + 1, j) && isSafe(mat, visited, i + 1, j)) {
max_dist = findLongestPath(mat, visited, i + 1, j, x, y,
max_dist, dist + 1);
}
if (isValid(i, j + 1) && isSafe(mat, visited, i, j + 1)) {
max_dist = findLongestPath(mat, visited, i, j + 1, x, y,
max_dist, dist + 1);
}
if (isValid(i - 1, j) && isSafe(mat, visited, i - 1, j)) {
max_dist = findLongestPath(mat, visited, i - 1, j, x, y,
max_dist, dist + 1);
}
if (isValid(i, j - 1) && isSafe(mat, visited, i, j - 1)) {
max_dist = findLongestPath(mat, visited, i, j - 1, x, y,
max_dist, dist + 1);
}
visited[i][j] = 0;
return max_dist;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int mat[][] = new int[M][N];
for(int i=0;i<M;i++)
for(int j=0;j<N;j++)
mat[i][j] = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
int d = sc.nextInt();
int[][] visited= new int[M][N];
int max_dist = findLongestPath(mat, visited, a, b, c, d, 0, 0);
System.out.println(max_dist);
}
}Solution: In Python 3
def isSafe(mat, visited, x, y):
return not (mat[x][y] == 0 or visited[x][y])
def isValid(x, y):
return M > x >= 0 and N > y >= 0
def findLongestPath(mat, visited, i, j, x, y, max_dist, dist):
if mat[i][j] == 0:
return 0
if i == x and j == y:
return max(dist, max_dist)
visited[i][j] = 1
if isValid(i + 1, j) and isSafe(mat, visited, i + 1, j):
max_dist = findLongestPath(mat, visited, i + 1, j, x, y, max_dist, dist + 1)
if isValid(i, j + 1) and isSafe(mat, visited, i, j + 1):
max_dist = findLongestPath(mat, visited, i, j + 1, x, y, max_dist, dist + 1)
if isValid(i - 1, j) and isSafe(mat, visited, i - 1, j):
max_dist = findLongestPath(mat, visited, i - 1, j, x, y, max_dist, dist + 1)
if isValid(i, j - 1) and isSafe(mat, visited, i, j - 1):
max_dist = findLongestPath(mat, visited, i, j - 1, x, y, max_dist, dist + 1)
visited[i][j] = 0
return max_dist
if __name__ == '__main__':
mat = [
[1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 1, 1, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
[1, 0, 0, 0, 1, 0, 0, 1, 0, 1],
[1, 0, 1, 1, 1, 1, 0, 0, 1, 1],
[1, 1, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 0, 1, 0, 0]
]
M = N = 10
visited = [[0 for x in range(N)] for y in range(M)]
max_dist = findLongestPath(mat, visited, 0, 0, 5, 7, 0, 0)
print(max_dist)Also Checkout