Print all possible paths from top left to bottom right of a mXn matrix in Python
By Aniket YadavIn this tutorial, we will write an algorithm followed by a complete program of how to print all possible paths from top left to bottom right of a mXn matrix in Python. So, here we will be given a matrix with m rows and n columns.
We will use a simple algorithm and call it again and again to have the required results. For each of the given matrix, we will first move through columns and then through rows to print the available paths. And then repeat it for each cell.
The function to rule:
We will use the given function to implement the above algorithm. The function name is “AllPaths”. Variables used are mat (the input matrix), x (counter for no. of rows), y (counter for no. of columns), path (for representing path).
In the first ‘if’ block of the function we will move towards the right of the matrix and store the elements of the matrix(mat) in the path. The path matrix is a matrix to define the final paths. Now we have reached to rightmost of the matrix.
In the second ‘if’ block we will move downward and again store the elements of the matrix(mat) in the path matrix.
Finally, we call the function again to get all the possible paths
def AllPaths(mat, x, y, m, n, path, pi):
if (x == m - 1):
for k in range(y, n):
path[pi + k - y] = mat[x][k]
for l in range(pi + n - y):
print(path[l], end = " ")
print()
return
if (y == n - 1):
for k in range(x, m):
path[pi + k - x] = mat[k][y]
for l in range(pi + m - x):
print(path[l], end = " ")
print()
return
path[pi] = mat[x][y]
AllPaths(mat, x + 1, y, m, n, path, pi + 1)
AllPaths(mat, x, y + 1, m, n, path, pi + 1)Complete code:
Here, we will use the above function and get the required output for a given matrix:
Given Matrix:
1 2 4 4 5 7
def AllPaths(mat, x, y, m, n, path, pi):
if (x == m - 1):
for k in range(y, n):
path[pi + k - y] = mat[x][k]
for l in range(pi + n - y):
print(path[l], end = " ")
print()
return
if (y == n - 1):
for k in range(x, m):
path[pi + k - x] = mat[k][y]
for l in range(pi + m - x):
print(path[l], end = " ")
print()
return
path[pi] = mat[x][y]
AllPaths(mat, x + 1, y, m, n, path, pi + 1)
AllPaths(mat, x, y + 1, m, n, path, pi + 1)
def AllPaths2(mat, m, n):
path = [0 for i in range(m + n)]
AllPaths(mat, 0, 0, m, n, path, 0)
mat = [[1, 2, 4],
[4, 5, 7]]
AllPaths2(mat, 2, 3)
Output:
1 4 5 7 1 2 5 7 1 2 4 7
Hi. Great tutorial, thanks.
I wonder how can I improve the code to allow all moves (up, left, down, right)
Example:
Input:
1 2 3
4 5 6
Output:
1 2 3 6
1 2 5 6
1 4 5 6
1 4 2 3 6