C++で最長のスネークシーケンスを見つける方法

概念

数値のグリッドが与えられたとき、その中から最大長のスネークシーケンス(Snake Sequence)を求め、表示する問題について解説します。最大長を持つスネークシーケンスが複数存在する場合は、そのうちのどれか1つを出力すれば構いません。

ここでいうスネークシーケンスとは、グリッド内の隣接する数値をつなげた列のことです。各数値に対して、その右側または下側にある数値が「+1」か「-1」の関係になっている必要があります。例えば、現在グリッド上の位置 (a, b) にいる場合、右隣の (a, b+1) の数値が ±1 であれば右へ移動でき、下の (a+1, b) の数値が ±1 であれば下へ移動できます。

具体例として、次のような4×4のグリッドを考えてみましょう。

10, 7, 6, 3
9, 8, 7, 6
8, 4, 2, 7
2, 2, 2, 8

このグリッドにおける最大のスネークシーケンスは (10, 9, 8, 7, 6, 7, 8) です。経路を図にすると以下のようになります。

10   7  → 6    3
↓   ↓   ↓
9  → 8  → 7  → 6
↓   ↓
8    4    2    7
↓
2    2    2    8

アルゴリズム(動的計画法)

この問題は動的計画法(Dynamic Programming)を使うことで効率的に解けます。基本的な考え方は次のとおりです。

• 行列の各セルについて、「そのセルで終わるスネークシーケンスの最長の長さ」を記録します。
• 表の中で最大の値を持つセルが、スネークの「尾(終端)」に対応します。
• スネーク全体を出力するには、尾から頭(始点)まで逆にたどり戻すバックトラックを行います。

T[a][b] をセル (a, b) で終わるスネークシーケンスの最大長とし、元の行列を M とすると、動的計画法の漸化式は次のように定義できます。

T[0][0] = 0
T[a][b] = max(T[a][b], T[a][b – 1] + 1)  if M[a][b] = M[a][b – 1] ± 1
T[a][b] = max(T[a][b], T[a – 1][b] + 1)  if M[a][b] = M[a – 1][b] ± 1

つまり、左隣または上隣のセルとの値の差が ±1 である場合に限り、そのセルの長さに1を加えたものを候補として比較し、大きい方を採用します。

C++による実装例

// C++ program to find maximum length
// Snake sequence and print it
#include <bits/stdc++.h>
using namespace std;
#define M 4
#define N 4
struct Point{
    int X, Y;
};
// スネークの尾(a, b)から頭までの経路を復元する関数
list<Point> findPath(int grid1[M][N], int mat1[M][N],
int a, int b){
    list<Point> path1;
    Point pt1 = {a, b};
    path1.push_front(pt1);
    while (grid1[a][b] != 0){
        if (a > 0 &&
        grid1[a][b] - 1 == grid1[a - 1][b]){
            pt1 = {a - 1, b};
            path1.push_front(pt1);
            a--;
        }
        else if (b > 0 &&
        grid1[a][b] - 1 == grid1[a][b - 1]){
            pt1 = {a, b - 1};
            path1.push_front(pt1);
            b--;
        }
    }
    return path1;
}
// 最長のスネークシーケンスを求める関数
void findSnakeSequence(int mat1[M][N]){
    // 部分問題の結果を格納するテーブル
    int lookup1[M][N];
    // 0で初期化
    memset(lookup1, 0, sizeof lookup1);
    // スネークシーケンスの最大長を保持
    int max_len1 = 0;
    // 尾の座標を保持
    int max_row1 = 0;
    int max_col1 = 0;
    // ボトムアップ方式でテーブルを埋める
    for (int a = 0; a < M; a++){
        for (int b = 0; b < N; b++){
            // セル(0, 0)以外を処理
            if (a || b){
                // 上方向を確認
                if (a > 0 &&
                abs(mat1[a - 1][b] - mat1[a][b]) == 1){
                    lookup1[a][b] = max(lookup1[a][b],
                    lookup1[a - 1][b] + 1);
                    if (max_len1 < lookup1[a][b]){
                        max_len1 = lookup1[a][b];
                        max_row1 = a, max_col1 = b;
                    }
                }
                // 左方向を確認
                if (b > 0 &&
                abs(mat1[a][b - 1] - mat1[a][b]) == 1){
                    lookup1[a][b] = max(lookup1[a][b],
                    lookup1[a][b - 1] + 1);
                    if (max_len1 < lookup1[a][b]){
                        max_len1 = lookup1[a][b];
                        max_row1 = a, max_col1 = b;
                    }
                }
            }
        }
    }
cout << "Maximum length of Snake sequence is: "
<< max_len1 << endl;
// 最長のスネークシーケンスの経路を求める
list<Point> path1 = findPath(lookup1, mat1, max_row1,
max_col1);
cout << "Snake sequence is:";
for (auto it = path1.begin(); it != path1.end(); it++)
cout << endl << mat1[it->X][it->Y] << " ("<< it->X << ", " << it->Y << ")" ;}
// ドライバコード
int main(){
    int mat1[M][N] ={{10, 7, 6, 3},{9, 8, 7, 6},{8, 4, 2, 7},{2, 2, 2, 8}};
    findSnakeSequence(mat1);
    return 0;
}

実行結果

このプログラムを実行すると、次の出力が得られます。

Maximum length of Snake sequence is: 6
Snake sequence is:
10 (0, 0)
9 (1, 0)
8 (1, 1)
7 (1, 2)
6 (1, 3)
7 (2, 3)
8 (3, 3)

まとめ

このアルゴリズムでは、M×N のグリッドに対して各セルを一度ずつ処理するため、時間計算量は O(M×N)、補助テーブル分の空間計算量も O(M×N) となります。動的計画法により部分問題の結果を再利用することで、全経路を総当たりする非効率な手法と比べて大幅に高速に最長スネークシーケンスを発見できる点がポイントです。