如何计算从mXn矩阵的左上角到右下角所有可能的路径？

2021年3月25日11:44:13 发表评论 1,380 次浏览

本文概述

问题是要打印从mXn矩阵的左上角到右下角的所有可能路径, 并且在每个单元格中, 你只能向右或向下移动.

例子 ：

Input : 1 2 3
        4 5 6
Output : 1 4 5 6
         1 2 5 6
         1 2 3 6

Input : 1 2 
        3 4
Output : 1 2 4
         1 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#

// 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 6
1 2 5 6
1 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)

输出如下：

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

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: