# 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:

## Java

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:

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

(1 votes, average: 5.00 out of 5)