指定された開始文字から辿る最長の連続パスを求めるアルゴリズム

異なる文字が格納された行列が与えられます。指定した一つの文字を起点として、現在の文字より「1つ大きい」連続する文字を順にたどりながら、最長のパスの長さを求めるのが本問題の目的です。

最長パスを探索するには深さ優先探索（DFS）が有効です。ただし、DFS をそのまま実行すると、同じ部分問題が何度も再計算されてしまう可能性があります。そこで動的計画法（メモ化）を併用し、一度計算した結果を保存して再利用することで、無駄な計算を省き効率化します。

入力と出力

Input:
上図のような文字行列と開始点を与えます。ここでは開始点を e とします。
Output:
Enter Starting Point (a-i): e
Maximum consecutive path: 5

開始点 e からは e → f → g → h → i という経路が作れるため、最長パス長は 5 となります。

アルゴリズム

findLongestLen(i, j, prev)

入力：位置 i と j、および直前の文字。
出力：その位置から始まる最長パスの長さ。

Begin
    if (i, j) が行列の範囲外、または prev と matrix[i][j] が連続していない場合
        return 0
    if longestPath[i][j] がすでに計算済みの場合
        return longestPath[i][j]
    len := 0

    for 周囲8方向の各セル k について do
        len := max(len, 1 + findLongestLen(i + x[k], j + y[k], matrix[i][j]))
    done

    longestPath[i][j] := len
    return len
End

getLen(start)

入力：開始点となる文字。
出力：全体での最大パス長。

Begin
    for 行列のすべての行 r について do
        for 行列のすべての列 c について do
            longestPath[r][c] := -1   // メモ配列を初期化

    len := 0
    for 行列のすべてのセル (i, j) について do
        if matrix[i][j] = start then
            for 周囲8方向の各セル k について do
                len := max(len, 1 + findLongestLen(i + x[k], j + y[k], start))
    return len
End

C++ による実装例

#include<iostream>
#define ROW 3
#define COL 3
using namespace std;

// 隣接セルへ再帰するための方向ベクトル
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);     // current と previous が連続しているか判定
}

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

このように、DFS で全方向への移動を再帰的に試しながら、メモ化によって部分問題の重複計算を排除することで、効率よく最長の連続パスを求められます。移動は上下左右に加えて斜め方向も含む周囲 8 方向が許容されている点がポイントです。