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

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

## 本文概述

``````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 = { {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

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

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]`````` 