C++で行列を移動する経路の数を数える方法

問題概要

行数 row × 列数 col の2次元行列が与えられます。目的は、セル (0,0) からセル (row, col) まで、「右」と「下」の移動のみを使って到達する方法が何通りあるかを数えることです。つまり、最初の移動は (0,0) → (0,1)(下方向)または (0,0) → (1,0)(右方向)のいずれかであり、(1,1) への斜め移動は認められません。

具体例

入力

col = 2; row = 4

出力

行列を移動する方法の数: 4

説明

セル (0,0) からセル (2,4) まで到達する経路は、以下の図のように表せます。

入力

col = 4; row = 3

出力

行列を移動する方法の数: 10

説明

この問題は、より小さな再帰問題へ分解して考えることができます。まず col=3、row=2 の場合の経路数を求め、次に col=2、row=1 の場合……というように順に計算していきます。col=1 または row=1 の場合、答えは必ず 1 になります(ひたすら右へ進むか、ひたすら下へ進むかのどちらかしか選べないため)。

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

このアプローチでは再帰を利用します。行(row)または列(col)のどちらかが 1 になった時点で、取り得る経路は「まっすぐ右へ進む」か「まっすぐ下へ進む」の 1 通りだけです。これを再帰の終了条件とします。

• 行列のサイズとして整数 row、col を受け取ります。
• 関数 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 はひとつ前の列番号です。
• 最終的に、すべての経路数の合計が得られます。

C++での実装例

#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<<"行列を移動する方法の数: "<<ways_traverse_matrix(row, col);
    return 0;
}

出力

上記のコードを実行すると、次のような出力が得られます。

行列を移動する方法の数: 2

補足:計算量と改善のヒント

上記の素朴な再帰では、同じ状態を何度も繰り返し計算するため、行列が大きくなるほど処理時間が急激に増加します。メモ化(動的計画法)を導入すれば各状態を一度だけ計算するようにでき、計算量を大幅に削減できます。また、数学的にはこの経路数は二項係数 C(row+col−2, row−1) と一致することが知られており、この性質を利用すればさらに効率的に答えを求めることが可能です。