如何计算从mXn矩阵的左上角到右下角所有可能的路径（） _数据结构

本文概述

C ++
Java
Python3
C#

【如何计算从mXn矩阵的左上角到右下角所有可能的路径（）】问题是要打印从mXn矩阵的左上角到右下角的所有可能路径, 并且在每个单元格中, 你只能向右或向下移动.
例子：

Input : 1 2 34 5 6Output : 1 4 5 61 2 5 61 2 3 6Input : 1 2 3 4Output : 1 2 41 3 4

该算法是一种简单的递归算法, 从每个单元格开始先向下打印所有路径, 然后再向右打印所有路径。对遇到的每个单元递归执行此操作。
以下是上述算法的实现。
C ++

// CPP program to Print all possible paths from // top left to bottom right of a mXn matrix #include< iostream> using namespace std; /* mat:Pointer to the starting of mXn matrix i, j: Current position of the robot (For the first call use 0, 0) m, n: Dimentions of given the matrix pi:Next index to be filed in path array *path[0..pi-1]: The path traversed by robot till now (Array to hold the path need to have space for at least m+n elements) */ void printAllPathsUtil( int *mat, int i, int j, int m, int n, int *path, int pi) { // Reached the bottom of the matrix so we are left with // only option to move right if (i == m - 1) { for ( int k = j; k < n; k++) path[pi + k - j] = *((mat + i*n) + k); for ( int l = 0; l < pi + n - j; l++) cout < < path[l] < < " " ; cout < < endl; return ; }// Reached the right corner of the matrix we are left with // only the downward movement. if (j == n - 1) { for ( int k = i; k < m; k++) path[pi + k - i] = *((mat + k*n) + j); for ( int l = 0; l < pi + m - i; l++) cout < < path[l] < < " " ; cout < < endl; return ; }// Add the current cell to the path being generated path[pi] = *((mat + i*n) + j); // Print all the paths that are possible after moving down printAllPathsUtil(mat, i+1, j, m, n, path, pi + 1); // Print all the paths that are possible after moving right printAllPathsUtil(mat, i, j+1, m, n, path, pi + 1); // Print all the paths that are possible after moving diagonal // printAllPathsUtil(mat, i+1, j+1, m, n, path, pi + 1); }// The main function that prints all paths from top left to bottom right // in a matrix 'mat' of size mXn void printAllPaths( int *mat, int m, int n) { int *path = new int [m+n]; printAllPathsUtil(mat, 0, 0, m, n, path, 0); }// Driver program to test abve functions int main() { int mat[2][3] = { {1, 2, 3}, {4, 5, 6} }; printAllPaths(*mat, 2, 3); return 0; }

Java

// Java program to Print all possible paths from // top left to bottom right of a mXn matrix public class MatrixTraversal {/* mat:Pointer to the starting of mXn matrix i, j: Current position of the robot (For the first call use 0, 0) m, n: Dimentions of given the matrix pi:Next index to be filed in path array *path[0..pi-1]: The path traversed by robot till now (Array to hold the path need to have space for at least m+n elements) */ private static void printMatrix( int mat[][], int m, int n, int i, int j, int path[], int idx) { path[idx] = mat[i][j]; // Reached the bottom of the matrix so we are left with // only option to move right if (i == m - 1 ) { for ( int k = j + 1 ; k < n; k++) { path[idx + k - j] = mat[i][k]; } for ( int l = 0 ; l < idx + n - j; l++) { System.out.print(path[l] + " " ); } System.out.println(); return ; }// Reached the right corner of the matrix we are left with // only the downward movement. if (j == n - 1 ) { for ( int k = i + 1 ; k < m; k++) { path[idx + k - i] = mat[k][j]; } for ( int l = 0 ; l < idx + m - i; l++) { System.out.print(path[l] + " " ); } System.out.println(); return ; } // Print all the paths that are possible after moving down printMatrix(mat, m, n, i + 1 , j, path, idx + 1 ); // Print all the paths that are possible after moving right printMatrix(mat, m, n, i, j + 1 , path, idx + 1 ); }// Driver code public static void main(String[] args) { int m = 2 ; int n = 3 ; int mat[][] = { { 1 , 2 , 3 }, { 4 , 5 , 6 } }; int maxLengthOfPath = m + n - 1 ; printMatrix(mat, m, n, 0 , 0 , new int [maxLengthOfPath], 0 ); } }

Python3

# Python3 program to Print all possible paths from # top left to bottom right of a mXn matrix''' /* mat: Pointer to the starting of mXn matrix i, j: Current position of the robot (For the first call use 0, 0) m, n: Dimentions of given the matrix pi: Next index to be filed in path array *path[0..pi-1]: The path traversed by robot till now (Array to hold the path need to have space for at least m+n elements) */ ''' def printAllPathsUtil(mat, i, j, m, n, path, pi):# Reached the bottom of the matrix # so we are left with only option to move right if (i = = m - 1 ): for k in range (j, n): path[pi + k - j] = mat[i][k]for l in range (pi + n - j): print (path[l], end = " " ) print () return# Reached the right corner of the matrix # we are left with only the downward movement. if (j = = n - 1 ):for k in range (i, m): path[pi + k - i] = mat[k][j]for l in range (pi + m - i): print (path[l], end = " " ) print () return# Add the current cell # to the path being generated path[pi] = mat[i][j]# Print all the paths # that are possible after moving down printAllPathsUtil(mat, i + 1 , j, m, n, path, pi + 1 )# Print all the paths # that are possible after moving right printAllPathsUtil(mat, i, j + 1 , m, n, path, pi + 1 )# Print all the paths # that are possible after moving diagonal # printAllPathsUtil(mat, i+1, j+1, m, n, path, pi + 1); # The main function that prints all paths # from top left to bottom right # in a matrix 'mat' of size mXn def printAllPaths(mat, m, n):path = [ 0 for i in range (m + n)] printAllPathsUtil(mat, 0 , 0 , m, n, path, 0 )# Driver Code mat = [[ 1 , 2 , 3 ], [ 4 , 5 , 6 ]]printAllPaths(mat, 2 , 3 )# This code is contributed by Mohit Kumar

// C# program to Print all possible paths from // top left to bottom right of a mXn matrix using System; public class MatrixTraversal {/* mat: Pointer to the starting of mXn matrix i, j: Current position of the robot (For the first call use 0, 0) m, n: Dimentions of given the matrix pi: Next index to be filed in path array *path[0..pi-1]: The path traversed by robot till now (Array to hold the path need to have space for at least m+n elements) */ private static void printMatrix( int [, ]mat, int m, int n, int i, int j, int []path, int idx) { path[idx] = mat[i, j]; // Reached the bottom of the matrix so we are left with // only option to move right if (i == m - 1) { for ( int k = j + 1; k < n; k++) { path[idx + k - j] = mat[i, k]; } for ( int l = 0; l < idx + n - j; l++) { Console.Write(path[l] + " " ); } Console.WriteLine(); return ; }// Reached the right corner of the matrix we are left with // only the downward movement. if (j == n - 1) { for ( int k = i + 1; k < m; k++) { path[idx + k - i] = mat[k, j]; } for ( int l = 0; l < idx + m - i; l++) { Console.Write(path[l] + " " ); } Console.WriteLine(); return ; }// Print all the paths that are possible after moving down printMatrix(mat, m, n, i + 1, j, path, idx + 1); // Print all the paths that are possible after moving right printMatrix(mat, m, n, i, j + 1, path, idx + 1); }// Driver code public static void Main(String[] args) { int m = 2; int n = 3; int [, ]mat = { { 1, 2, 3 }, { 4, 5, 6 } }; int maxLengthOfPath = m + n - 1; printMatrix(mat, m, n, 0, 0, new int [maxLengthOfPath], 0); } }// This code contributed by Rajput-Ji

输出如下：

1 4 5 61 2 5 61 2 3 6

请注意, 在上面的代码中, 对printAllPathsUtil()的最后一行进行了注释。如果我们取消注释此行, 则如果还允许对角线移动, 则将获得从nXm矩阵的左上角到右下角的所有路径。而且, 如果不允许移动到某些单元格, 则可以通过将限制数组传递给上述函数来改进相同的代码, 这留作练习。
本文作者：哈里普拉萨德(NG)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
Python实现

# Python3 program to Print all possible paths from # top left to bottom right of a mXn matrix allPaths = [] def findPaths(maze, m, n): path = [ 0 for d in range (m + n - 1 )] findPathsUtil(maze, m, n, 0 , 0 , path, 0 )def findPathsUtil(maze, m, n, i, j, path, indx): global allPaths # if we reach the bottom of maze, we can only move right if i = = m - 1 : for k in range (j, n): #path.append(maze[i][k]) path[indx + k - j] = maze[i][k] # if we hit this block, it means one path is completed. # Add it to paths list and print print (path) allPaths.append(path) return # if we reach to the right most corner, we can only move down if j = = n - 1 : for k in range (i, m): path[indx + k - i] = maze[k][j] #path.append(maze[j][k]) # if we hit this block, it means one path is completed. # Add it to paths list and print print (path) allPaths.append(path) return# add current element to the path list #path.append(maze[i][j]) path[indx] = maze[i][j]# move down in y direction and call findPathsUtil recursively findPathsUtil(maze, m, n, i + 1 , j, path, indx + 1 )# move down in y direction and call findPathsUtil recursively findPathsUtil(maze, m, n, i, j + 1 , path, indx + 1 )if __name__ = = '__main__' : maze = [[ 1 , 2 , 3 ], [ 4 , 5 , 6 ], [ 7 , 8 , 9 ]] findPaths(maze, 3 , 3 ) #print(allPaths)

输出如下：