Find all paths from first cell to last cell of a matrix

Given a M x N matrix, find all paths from first cell to last cell. We can only move down or to the right from the current cell.


For example,

Input:

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

Output:
1 – 2 – 3 – 6 – 9
1 – 2 – 5 – 6 – 9
1 – 2 – 5 – 8 – 9
1 – 4 – 5 – 6 – 9
1 – 4 – 5 – 8 – 9
1 – 4 – 7 – 8 – 9

 


 
We can easily solve this problem using recursion. The idea is to start from the top-left cell of the matrix and recuse for next node (immediate right or immediate bottom cell) and keep on doing that for every visited cell till destination is reached. We maintain a path array to store the nodes in current path and update the path array (include current node in it) whenever we visit any cell. Whenever destination (bottom-right corner) is reached, we print the path array.

C++

Download   Run Code

Output:

1 – 2 – 3 – 6 – 9
1 – 2 – 5 – 6 – 9
1 – 2 – 5 – 8 – 9
1 – 4 – 5 – 6 – 9
1 – 4 – 5 – 8 – 9
1 – 4 – 7 – 8 – 9


 

Time complexity of above solution is exponential.

T(M, N) = T(M, N-1) + T(N, M-1) // for two recursive calls
T(M, 1) = M, T(1, N) = N, T(1, 1) = 1

Auxiliary space used by the program is O(M + N).

 
If we carefully analyze the solution, we can see the problem has overlapping sub-problems. So it can be solved using Dynamic Programming and time complexity can be reduced drastically (space complexity will also increase drastically).

 
Exercise:

1. Make above code memory efficient. (Hint – Pass vector by reference and use Backtracking)

2. Convert above solution to DP using memoization.

3. Convert above code to C language using array to store path information.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Vivek Pal
Vivek Pal

Exercise 1 solution (pass by reference and backtrack): http://cpp.sh/72fh

wpDiscuz