C++で指定された制約を満たす行列内の最長パスを検索する方法

n次の正方行列を考えます。この行列にはすべて異なる要素が含まれています。ここで、パス上のすべてのセルが差1で増加順に並ぶような最長パスを求める必要があります。あるセルからは、左・右・上・下の4方向に移動できます。例えば、次のような行列があるとします。

この場合の出力は 4 になります。最長パスは 6→7→8→9 となるためです。

解法のアプローチ

この問題を解くためには、次の考え方に従います。まず、すべてのセルから始まる最長パスを計算します。すべてのセルについて最長パスが求まったら、その中の最大値を返します。

このアプローチで重要なポイントは、多くの重複する部分問題が存在することです。したがって、この問題は動的計画法（Dynamic Programming）を用いて効率的に解くことができます。ここでは、ルックアップテーブル dp[][] を使用して、ある問題がすでに解決済みかどうかを確認します。

実装例

#include <iostream>
#define n 3
using namespace std;
int getLongestPathLengthUtil(int i, int j, int matrix[n][n], int table[n][n]) {
    if (i < 0 || i >= n || j < 0 || j >= n)
    return 0;
    if (table[i][j] != -1)
        return table[i][j];
    int x = INT_MIN, y = INT_MIN, z = INT_MIN, w = INT_MIN;
    if (j < n - 1 && ((matrix[i][j] + 1) == matrix[i][j + 1]))
        x = 1 + getLongestPathLengthUtil(i, j + 1, matrix, table);
    if (j > 0 && (matrix[i][j] + 1 == matrix[i][j - 1]))
        y = 1 + getLongestPathLengthUtil(i, j - 1, matrix, table);
    if (i > 0 && (matrix[i][j] + 1 == matrix[i - 1][j]))
        z = 1 + getLongestPathLengthUtil(i - 1, j, matrix, table);
    if (i < n - 1 && (matrix[i][j] + 1 == matrix[i + 1][j]))
        w = 1 + getLongestPathLengthUtil(i + 1, j, matrix, table);
        return table[i][j] = max(x, max(y, max(z, max(w, 1))));
}
int getLongestPathLength(int matrix[n][n]) {
    int result = 1;
    int table[n][n];
    for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    table[i][j] = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (table[i][j] == -1)
            getLongestPathLengthUtil(i, j, matrix, table);
            result = max(result, table[i][j]);
        }
    }
    return result;
}
int main() {
    int mat[n][n] = { { 1, 2, 9 },
    { 5, 3, 8 },
    { 4, 6, 7 } };
    cout << "Length of the longest path is "<< getLongestPathLength(mat);
}

実行結果

Length of the longest path is 4

計算量について

メモ化により各セルの結果は一度だけ計算されるため、このアルゴリズムの時間計算量は O(n²) となり、行列のサイズが大きくなっても効率的に動作します。