C++で行列の左上から右下へのすべての回文パスを出力する方法

この問題では、小文字のアルファベットのみで構成された行列が与えられ、その行列の左上から右下までのすべての回文パスを見つけて出力することが求められます。

移動として許可されているのは右方向と下方向のみで、斜め移動は認められていません。

問題の例

具体例を使って問題を理解しましょう。

入力: matrix[][] = {
    {"xxxy",
    "yxxx",
    "xyyx"}
出力: xxxxxx, xxxxxx, xyxxyx

解説

左上から右下へのすべての有効な移動経路を、セルの位置 i を使って確認してみましょう。

i00 -> i01 -> i02 -> i03 -> i13 -> i23 = xxxyxx
i00 -> i01 -> i11 -> i12 -> i13 -> i23 = xxxxxx
.
.
.
i00 -> i10 -> i20 -> i21 -> i22 -> i23 = xyxyyx

考えられるすべての経路の中から、回文になっているパスのみを抽出します。

i00 -> i01 -> i11 -> i12 -> i13 -> i23 = xxxxxx
i00 -> i01 -> i02 -> i12 -> i13 -> i23 = xxxxxx
i00 -> i10 -> i11 -> i12 -> i22 -> i23 = xyxxyx

この説明の中に、すでに解法の基礎が示されています。つまり、左上から右下へのすべての経路を探索し、そのうち回文となるパスだけを出力すればよいのです。

実装例

以下のC++コードは、再帰を用いてすべての経路を探索し、回文判定を行う解法を示しています。

#include<iostream>
using namespace std;
#define N 4

// 文字列が回文かどうかを判定し、回文であれば出力する
int printPalindrome(string str){
    int len = str.length() / 2;
    for (int i = 0; i < len; i++) {
        if (str[i] != str[str.length() - i - 1])
        return 0;
    }
    cout<<str<<endl;
}

// 左上から右下へのすべての経路を再帰的に探索する
void findPath(string str, char a[][N], int i, int j, int m, int n) {
    if (j < m - 1 || i < n - 1) {
        if (i < n - 1)
        findPath(str + a[i][j], a, i + 1, j, m, n);  // 下へ移動
        if (j < m - 1)
        findPath(str + a[i][j], a, i, j + 1, m, n);  // 右へ移動
    } else {
        str = str + a[n - 1][m - 1];  // 右下のセルを追加して完成
        printPalindrome(str);
    }
}

int main() {
    char matrix[][N] = {
        { 'x', 'y', 'x', 'y' },
        { 'y', 'x', 'x', 'y' },
        { 'y', 'x', 'y', 'x' }
    };
    string str = "";
    cout<<"回文パスは次の通り: ";
    findPath(str, matrix, 0, 0, 4, 3);
    return 0;
}

出力結果

回文パスは次の通り: xyxxyx
xyxxyx
xyxxyx
xyxxyx
xyxxyx
xyxxyx
xyxxyx
xyxxyx

アルゴリズムのポイント

この解法は深さ優先探索（DFS）をベースにしています。各セルに到達した時点で、下方向と右方向の2つの選択肢を再帰的に試すことで、すべての経路を網羅的に探索できます。経路が右下のセルに到達した時点で文字列が完成し、printPalindrome関数によって回文判定が行われます。

計算量は経路の総数に依存し、m×nの行列の場合、経路の数は二項係数 C(m+n-2, m-1) に比例するため、行列が大きくなると指数的に増加することに注意が必要です。