C++でマトリックスをトラバースする方法の数を数えます

例

入力

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つのまっすぐ下への移動という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<<"Count the number of ways to traverse a Matrix are: "<<ways_traverse_matrix(row, col);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count the number of ways to traverse a Matrix are: 2