计算在 C++ 中遍历矩阵的方法数

给定一个维度为 X col 的二维矩阵。目标是计算从单元格 0,0 到单元格行、col 仅使用向右和向下移动可以遍历矩阵的方式数，即第一次移动可以是 0,0 到 0,1（向下）或 1,0 （右）而不是 1,1（对角线）。

例如

输入

col = 2; row = 4

输出结果

Count of number of ways to traverse a Matrix are: 4

解释

显示了我们可以从单元格 0,0 到达 2,4 的方式 -

输入

col = 4; row = 3

输出结果

Count of number of ways to traverse a Matrix are: 10

解释

We will reduce the problem into smaller recursions. Count ways for
col=3, row=2, then for col=2, row=1 ….. For col=1 or row=1 the answer will be 1. (only right or only down move).

以下程序中使用的方法如下

在这种方法中，我们将使用递归方法。在行或列的末尾为 1。只有一种方式是 1 笔直右移动或 1 笔直下移动。这将是递归的终止条件。

• 取整数行，列作为矩阵的维度。

• 函数ways_traverse_matrix(int row, int col)获取维度并返回遍历矩阵的方式数。

• 对于 row==1，返回 1。

• 对于 col==1，返回 1。

• 否则使用递归ways_traverse_matrix(temp_1, col) +ways_traverse_matrix(row, temp_2) 计算方式。

• 这里 temp_1=上一个行号和 temp_2=上一个列号。

• 最后，我们将计算总路数。

示例

#include <bits/stdc++.h>
using namespace std;
int ways_traverse_matrix(int row, int col){
   if (row == 1){
      return 1;
   }
   else if(col == 1){
      return 1;
   } else {
      int temp_1 = row − 1;
      int temp_2 = col − 1;
      return ways_traverse_matrix(temp_1, col) + ways_traverse_matrix(row, temp_2);
   }
}
int main(){
   int col = 2;
   int row = 2;
   cout<<"计算遍历 Matrix 的方式有： "<<ways_traverse_matrix(row, col);
   return 0;
}

输出结果

如果我们运行上面的代码，它将生成以下输出 -

计算遍历 Matrix 的方式有： 2