C++で4方向の移動を許可して、行列の左上から右下までのすべての経路を出力する方法

問題の概要

この問題では、m×n の2次元行列が与えられ、行列の左上のセルから右下のセルまでの、取り得るすべての経路を出力することを目標とします。移動として許可されているのは、左・右・上・下の4方向です。

実際には「右」と「上」への移動はあまり使われることがありませんが、状況によっては有効に働くこともあります。

具体例

まず、例を見ながら内容を理解しましょう。

入力：

1 3 5

2 8 9

出力：

1 -> 3 -> 5 -> 9
1 -> 3 -> 8 -> 9
1 -> 2 -> 8 -> 9

解法のアプローチ

この問題は、あるセルから隣接するセルへ順番に移動しながら、下方向と右方向へ進んだ時点での経路を出力していくことで解決できます。この処理を、行列内の各セルに対して再帰的に繰り返します。

具体的には、以下のような流れになります。

• 現在位置が最下行に達した場合 → 残りの列の値をすべて経路に追加して出力し、処理を終了します。
• 現在位置が最右列に達した場合 → 残りの行の値をすべて経路に追加して出力し、処理を終了します。
• それ以外の場合 → 現在のセルの値を経路に記録したうえで、「下へ進む」場合と「右へ進む」場合の2つの再帰呼び出しを行います。

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<<"Path from top-left to bottom-right of matrix are :\n";
    findPath(*mat, 2, 3);
    return 0;
}

実行結果

Path from top-left to bottom-right of matrix are :
1 4 5 6
1 2 5 6
1 2 3 6

補足：4方向の移動を扱う際の注意点

上記のコード例では、基本となる「下」と「右」の2方向のみを実装しています。しかし、すべての4方向の移動を許可する場合は注意が必要です。左や上への移動を許すと、同じセルを何度も訪れて無限ループ（無限再帰）に陥る可能性があります。

そこで一般的には、各セルがすでに訪問済みかどうかを記録する visited 配列を用意し、一度通ったセルは再訪しないよう制御します。こうすることで、4方向すべての移動を安全に探索できるようになります。

また、取り得る経路の総数は行列のサイズに対して指数関数的に増加するため、大きな行列を扱う場合は計算量にも十分留意してください。