C++で指定した開始文字から最長の連続パスの長さを求める方法

異なる文字が格納された行列（マトリックス）が与えられます。ある文字を起点として、現在の文字より1つ大きい連続した文字（例：a→b→c→d）をたどりながら、最長のパスの長さを見つけることが課題です。移動は、縦・横・斜めを含む8方向の隣接セルに対して可能です。

例えば、下図のような行列が与えられ、開始文字を「E」とします。

この行列で開始文字「e」から探索すると、最長の連続パスの長さは5となります。

アルゴリズムの考え方

最長パスを見つけるには、深さ優先探索（DFS）アルゴリズムを使用します。DFSの実行中には、同じ部分問題が何度も発生することがあります。このような部分問題を繰り返し計算しないようにするため、動的計画法（メモ化）のアプローチを採用します。一度計算した結果を longestPath 配列にキャッシュすることで、計算量を大幅に削減できます。

C++での実装例

#include<iostream>
#define ROW 3
#define COL 3
using namespace std;
// 隣接セルを再帰的に探索するための8方向の移動量
int x[] = {0, 1, 1, -1, 1, 0, -1, -1};
int y[] = {1, 0, 1, 1, -1, -1, 0, -1};
int longestPath[ROW][COL];
char mat[ROW][COL] = {
    {'a','c','d'},
    {'h','b','a'},
    {'i','g','f'}
};
int max(int a, int b){
    return (a>b)?a:b;
}
bool isvalid(int i, int j){
    if (i < 0 || j < 0 || i >= ROW || j >= COL) // i と j が範囲外の場合
    return false;
    return true;
}
bool isadjacent(char previous, char current){
    return ((current - previous) == 1); // 文字が連続しているかチェック
}
int findLongestLen(int i, int j, char prev){
    if (!isvalid(i, j) || !isadjacent(prev, mat[i][j]))
        // 範囲外または連続していない場合
        return 0;
    if (longestPath[i][j] != -1)
    return longestPath[i][j]; // 部分問題はすでに解決済み
    int len = 0; // 結果を 0 で初期化
    for (int k=0; k<8; k++) // 最長パスの長さを再帰的に求める
    len = max(len, 1 + findLongestLen(i + x[k], j + y[k], mat[i][j]));
        return longestPath[i][j] = len; // 長さを保存して返す
}
int getLen(char start){
    for(int i = 0; i<ROW; i++)
    for(int j = 0; j<COL; j++)
    longestPath[i][j] = -1; // すべての要素を -1 で初期化
    int len = 0;
    for (int i=0; i<ROW; i++){
        for (int j=0; j<COL; j++){ // すべての開始候補をチェック
            if (mat[i][j] == start) {
                for (int k=0; k<8; k++) // 8方向の隣接セルをすべて調べる
                len = max(len, 1 + findLongestLen(i + x[k], j + y[k], start));
                }
            }
    }
    return len;
}
int main() {
    char start;
    cout << "Enter Starting Point (a-i): "; cin >> start;
    cout << "Maximum consecutive path: " << getLen(start);
    return 0;
}

出力結果

Enter Starting Point (a-i): e
Maximum consecutive path: 5

コードの解説

isvalid()：指定されたセルが行列の範囲内にあるかどうかを判定します。範囲外の場合は false を返します。

isadjacent()：現在の文字が前の文字より文字コードで1つ大きいか、つまり連続した文字（例：a→b）になっているかをチェックします。

findLongestLen()：指定セルから再帰的に最長パスを探索する核心的な関数です。すでに計算済みのセル（longestPath[i][j] != -1）は、保存された結果をそのまま返すことで再計算を回避します。

getLen()：行列内で開始文字と一致するすべてのセルを起点として探索を行い、得られた最長の長さを返します。

計算量について

メモ化により各セルの計算は一度だけ行われるため、時間計算量は O(ROW × COL × 8)、すなわち O(ROW × COL) となります。動的計画法を用いない素朴なDFSでは、最悪の場合に指数時間かかる可能性がありますが、メモ化を組み合わせることで効率的に解くことができます。