C++で行列内の指定されたスコアに到達する方法の数を数える

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

開始地点は matrix[0][0] であり、そこから移動できるのは matrix[0][1](右移動)または matrix[1][0](下移動)のいずれかです。通過した要素の値を順に加算し、合計が score と一致するようにします。

例を使って理解しよう

例1

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

出力 − 行列内の指定されたスコアに到達する方法の数: 2

説明 − スコアは以下の2つの方法で到達できます。

方法1: インデックス (0,0) + (0,1) + (1,1) の要素を加算 = 1+1+1 = 3

方法2: インデックス (0,0) + (1,0) + (1,1) の要素を加算 = 1+1+1 = 3

例2

入力 − matrix[row][col] = { {1,1,2}, {2,1,1}, {1,2,2} }、score = 7

出力 − 行列内の指定されたスコアに到達する方法の数: 2

説明 − スコアは以下の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

プログラムで使用するアプローチ

このアプローチでは、動的計画法(DP)を用いて問題を解きます。2つの配列 arr[row][col][size] と check[row][col][size] を使用します。check 配列は、matrix[][] の各セルが訪問済みであることを true としてマークするために使い、arr[][][] 配列は、matrix[0][0] から特定のセルに到達する方法の数を格納するために使用します。方法の数は再帰的に計算していきます。

• 数値を格納するための2次元配列 matrix を用意します。
• 変数 score を入力として受け取ります。
• int arr[row][col][size] と bool check[row][col][size] の2つの配列を用意します。
• 関数 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