Longest Route

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
19 upvotes
Asked in companies
HSBCFacebookTata1mg

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
3 3
1 1 0
0 1 1
1 0 1
0 0
2 2
Sample Output 1:
4
Explanation for Sample Input 1:
The only and longest path is  :  (0,0) -> (0,1) -> (1,1) -> (1,2) -> (2,2)

sample 1

Sample Input 2:
3 3
0 1 0
0 1 1
1 0 1
0 0
2 2
Sample Output 2:
-1
Hint

Use a backtracking solution while keeping track of visited cells

Approaches (1)
Brute Force


 

  1. 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.
  2. 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.
  3. 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).
  4. 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
Time Complexity

O(n+m)!) where ‘n’ and ‘m’ are dimensions of the given matrix.

 

The total number of paths from the top-left corner to reach the bottom-right corner of a matrix is (N+M-2) C (N-1).

Space Complexity

O(n*m) where ‘n’ and ‘m’ are the dimensions of the given matrix.

 

Since the only additional space, we are using is while building the visited matrix, which has NxM cells, thus complexity is O(N*M)

Code Solution
(100% EXP penalty)
Longest Route
Full screen
Console