C++でm×n行列の左上から右下までの全経路を再帰的に出力する方法

はじめに

本記事では、m×n の2次元行列が与えられたとき、その左上（先頭要素）から右下（最終要素）まで移動可能なすべての経路を C++ で出力する方法を解説します。

ただし、移動は以下の2方向に制限されるものとします。

• 右へ1マス移動
• 下へ1マス移動

問題の例

まず、具体例を使って問題を確認しましょう。

入力:
1 3 5
2 8 9

出力:
1 -> 3 -> 5 -> 9
1 -> 3 -> 8 -> 9
1 -> 2 -> 8 -> 9

このように、左上の「1」からスタートして右下の「9」に到達できる経路がすべて列挙されます。

アルゴリズムの考え方

この問題は再帰（バックトラッキング）を使うことでシンプルに解けます。基本的な流れは次のとおりです。

1. 現在のセルの値を経路配列 path に記録します。
2. 下方向に移動できる場合は、下へ進む再帰呼び出しを行います。
3. 右方向に移動できる場合は、右へ進む再帰呼び出しを行います。
4. 現在位置が最終行に達した場合、残りは右に進むしかないため、右端までの値を経路に追加して出力します。
5. 同様に、現在位置が最終列に達した場合も、下端までの値を経路に追加して出力します。

なお、経路の長さは最大でも「行数 + 列数 − 1」となるため、path 配列のサイズは m + n で十分です。

C++での実装例

上記の再帰アルゴリズムを実装したプログラムがこちらです。

#include<iostream>
using namespace std;

void printPathTPtoBR(int *mat, int i, int j, int m, int n, int *path, int pi) {
    // 最終行に到達した場合：右端まで進んで経路を出力
    if (i == m - 1) {
        for (int k = j; k < n; k++)
            path[pi + k - j] = *((mat + i*n) + k);
        for (int l = 0; l < pi + n - j; l++)
            cout << path[l] << " ";
        cout << endl;
        return;
    }
    // 最終列に到達した場合：下端まで進んで経路を出力
    if (j == n - 1) {
        for (int k = i; k < m; k++)
            path[pi + k - i] = *((mat + k*n) + j);
        for (int l = 0; l < pi + m - i; l++)
            cout << path[l] << " ";
        cout << endl;
        return;
    }
    // 現在のセルを経路に記録し、「下」と「右」の両方向を再帰的に探索
    path[pi] = *((mat + i*n) + j);
    printPathTPtoBR(mat, i+1, j, m, n, path, pi + 1);
    printPathTPtoBR(mat, i, j+1, m, n, path, pi + 1);
}

void findPath(int *mat, int m, int n) {
    int *path = new int[m+n];
    printPathTPtoBR(mat, 0, 0, m, n, path, 0);
}

int main() {
    int mat[2][3] = { {1, 2, 3}, {4, 5, 6} };
    cout<<"行列の左上から右下までの経路一覧 :\n";
    findPath(*mat, 2, 3);
    return 0;
}

実行結果

上記プログラムの出力は以下のようになります。

1 4 5 6
1 2 5 6
1 2 3 6

まとめ

m×n 行列における左上から右下への全経路の列挙は、再帰処理によって簡潔に実装できます。各セルで「下」「右」の2択を試すバックトラッキングの考え方は、迷路探索やパズル系の問題にも応用できる重要なテクニックなので、ぜひ理解しておきましょう。