Print all shortest routes in a rectangular grid

Given a M x N rectangular grid, print all shortest routes in the grid that start at the first cell (0,0) and end at the last cell (N-1,M-1). We can move down or right or diagonally (down-right) but not up or left.


 

For example,


Input:

{ 1, 2, 3 }
{ 4, 5, 6 }
{ 7, 8, 9 }

Output:

[ 1, 4, 7, 8, 9 ]
[ 1, 4, 5, 8, 9 ]
[ 1, 4, 5, 6, 9 ]
[ 1, 4, 5, 9 ]
[ 1, 4, 8, 9 ]
[ 1, 2, 5, 8, 9 ]
[ 1, 2, 5, 6, 9 ]
[ 1, 2, 5, 9 ]
[ 1, 2, 3, 6, 9 ]
[ 1, 2, 6, 9 ]
[ 1, 5, 8, 9 ]
[ 1, 5, 6, 9 ]
[ 1, 5, 9 ]

 

 
The idea is to use recursion to find all routes. We start from the source cell (top-left corner) of the grid and recurse for the next nodes. The next node can be either of immediate right cell, immediate bottom cell, or immediate down-right diagonal cell. We recursively repeat this for every visited cell till the destination is reached. We maintain a data structure to store nodes in the current route and print the path whenever destination cell (bottom-right corner) is reached.

Here’s code to print all such paths in C++ and Java:

C++

Download   Run Code

Java

Download   Run Code

 
The time complexity of above solution is exponential.


T(M, N) = T(M, N-1) + T(M-1, N) + T(M-1, N-1)
T(M, 1) = M
T(1, N) = N
T(1, 1) = 1

 
The auxiliary space required by the program is O(M + N).

 
There is another variation of the above problem where we need to print only those paths which lies above the diagonal x = y. For example, following paths are valid for the above matrix.

[1, 2, 3, 6, 9]
[1, 2, 5, 6, 9]
[1, 2, 5, 9]
[1, 2, 6, 9]
[1, 5, 6, 9]
[1, 5, 9]

 
In order for a path to be valid, at all points (x,y) on the path, x should be less than y. We can simply enforce this constraint while building the paths. This is demonstrated below in C++ and Java:

C++ code and Java code.

 
Exercise: Efficiently count total number of possible paths from top-left corner to bottom-right corner of a matrix using Dynamic Programming.

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of