C++のマトリックスで特定のスコアに到達する方法の数を数えます

要素として非負の数を含む正方行列[][]が与えられます。また、可変スコアが与えられます。目標は、matrix [] []から要素を追加して、指定されたスコアに到達する方法を数えることです。これにより、許可される移動は右移動と下移動のみになります。

matrix [0] [0]から開始して、移動のみが可能です。matrix[0] [1]（右移動）に移動するか、matrix [1] [0]（下移動）に移動し、値を追加してsum=scoreに到達します。

例を挙げて理解しましょう。

例

入力- matrix [row] [col] ={{1、1}、{1、1}} score =3

出力- マトリックス内の特定のスコアに到達する方法の数は次のとおりです。2

説明- スコアには次の方法で到達できます：

方法1：インデックス（0,0）+（0,1）+（1,1）=1 + 1 + 1=3に要素を追加する

方法2：インデックス（0,0）+（1,0）+（1,1）=1 + 1 + 1=3に要素を追加する

入力- matrix [row] [col] ={{1,1,2}、{2,1,1}、{1,2,2}}スコア=7

出力- マトリックス内の特定のスコアに到達する方法の数は次のとおりです。2

説明- スコアには次の方法で到達できます：

方法1：インデックス（0,0）+（0,1）+（1,1）+（1,2）+（2,2）=1 + 1 + 1 + 2 + 2 =7

方法2：インデックス（0,0）+（0,1）+（1,1）+（2,1）+（2,2）=1 + 1 + 1 + 2 + 2=7に要素を追加する

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、動的計画法を使用して問題を解決します。 2つの配列arr[row][col][size]とcheck[row][col] [size]を使用します。配列チェックは、行列[][]のセルがtrueとしてアクセスされた場合にそれらをマークします。配列arr[][] []は、matrix[0][0]から特定のセルに到達するための方法の数を格納するために使用されます。再帰的に方法を計算します。

• 数値を格納するために2D配列行列を使用します。
• 変数スコアを入力として使用します。
• 2つの配列intarr[row][col][size]とboolcheck[row][col][size]を取得します。
• 関数matrix_score（int matrix [row] [col]、int rows、int cols、int sc）は、マトリックス内の特定のスコアに到達する方法の数を返すために使用されます。
• スコアscが0未満の場合は、0を返します。（再帰を終了するため、または入力が間違っている場合）
• 行または列の数が0未満の場合は、0を返します（再帰を終了します）。
• 最初のセルがsc（入力スコア）と等しい場合は、唯一の方法として1を返します。そうでない場合は、0を返します。
• 現在のセルがすでにアクセスされている場合は、このセルでのウェイの数をarr [rows][cols][sc]として返します。
• 上記のすべての条件が満たされない場合は、現在のセルに訪問済みのマークを付けます。 check [rows] [cols] [sc]=trueを使用します。
• temp_1 =matrix_score（matrix、rows-1、cols、sc-matrix [rows] [cols]）を計算します
• temp_2 =matrix_score（matrix、rows、cols-1、sc-matrix [rows] [cols]）を計算します
• ウェイの数をarr[rows][cols] [sc] =temp_1+temp_2として設定します。
• 最後にarr[rows][cols][sc]を返します。

例

#include <iostream>

using namespace std;
#define row 2
#define col 2
#define size 30
int arr[row][col][size];
bool check[row][col][size];

int matrix_score(int matrix[row][col], int rows, int cols, int ways) {
   if (ways < 0) {
      return 0;
   }
   if (rows < 0 || cols < 0) {
      return 0;
   }
   if (rows == 0) {
      if (cols == 0) {
         if (ways == matrix[0][0]) {
            return 1;
         } else {
            return 0;
         }
      }
   }
   if (check[rows][cols][ways]) {
      return arr[rows][cols][ways];
   }
   check[rows][cols][ways] = true;
   int temp_1 = matrix_score(matrix, rows - 1, cols, ways - matrix[rows][cols]);
   int temp_2 = matrix_score(matrix, rows, cols - 1, ways - matrix[rows][cols]);
   arr[rows][cols][ways] = temp_1 + temp_2;
   return arr[rows][cols][ways];
}
int main() {
   int matrix[row][col] = {
      {
         1,
         1
      },
      {
         1,
         1
      }
   };
   int ways = 3;
   cout << "Count of number of ways to reach a given score in a Matrix are: " << matrix_score(matrix, row - 1, col - 1, ways);
   return 0;
}

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

出力

Count of number of ways to reach a given score in a Matrix are: 2