Last Updated: 16 Feb, 2021
Longest Route
Moderate
Asked in companies
You are given a 2-D binary matrix "Mat" of dimensions N x M consisting only of 0s and 1s. The cell consisting of 0 means that the cell is blocked and it cannot be visited whereas a cell with 1 as a value means it can be visited.
You are given a source cell and a destination cell. You need to find the length of the longest possible path from source to destination, given you can only move in 4 possible directions north(i.e from (i,j) to (i-1,j)), south(i.e from (i,j) to (i+1,j)), east(i.e from (i,j) to (i,j-1)), and west(i.e from (i,j) to (i,j+1)), and without visiting a cell twice.
Note:
1. If the move isn’t possible you remain in that cell only.
Input Format:
The first line of the input contains two space-separated integers 'N' and ‘M’, denoting the number of rows and columns of the matrix respectively.
Next, there will be N lines each containing M space-separated integers denoting the description of the matrix.
The next line contains two space-separated integers ‘Sx’, ‘Sy’ denoting the indexes of the source cell
The next line contains two space-separated integers ‘Dx’, ‘Dy’ denoting the indexes of the destination cell
Output Format:
If a path exists then print the length of the longest possible path from source to destination.
Otherwise, print -1.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= N, M <= 12 , such that N+M <=12
0 <= Mat[i][j] <= 1 ,
0 <= Sx, Dx <= N-1
0 <= Sy, Dy <= M-1
Where Mat[i][j] is the value at position i,j in the matrix.
Approaches
- The idea is to reduce the problem from finding a path from source to destination to finding a path from some node to destination and building our answer up.
- From the current cell, we look if there exists a neighbor from where I can reach the destination if no such neighbor exists we return -1.
- Else if a path exists we take the longest path then add 1 in it ( to account for the transition from the current cell to a neighbor).
- In the end, we change the visited current node to false and return the answer.
The algorithm will be like this:
- If we have already visited the node or if the value at the position is ‘0’ then return -1.
- If we have reached the destination return 0
- Mark visited as true at the current position and initialize answer as -1
- Move-in all four directions (N, S, E, W) and find the longest path from the positions.
- Since the new position is distance 1 away from the longest path from the current position will be 1+ max( longest path from all four directions if it exists i.e. all non-negative values ).
- Mark visited as false
- Return the answer