C++で解くセルフクロッシング問題 ― 経路の自己交差を判定するアルゴリズム

問題の概要

n個の数値からなる配列 x があるとします。点 (0, 0) を出発点として、まず x[0] 単位だけ北へ移動し、続いて x[1] 単位だけ西へ、x[2] 単位だけ南へ、x[3] 単位だけ東へ……というように移動を繰り返します。つまり、1回移動するごとに進行方向は反時計回りに90度変化していきます。このとき、追加の記憶領域を O(1) しか使わないワンパス（1回の走査）アルゴリズムを設計し、描かれる経路が自分自身と交差するかどうかを判定してください。

例えば、配列が [3, 4, 2, 5] の場合は次のようになります。

この場合、経路は自分自身と交差するため、答えは true になります。

交差が起こる3つのパターン

反時計回りの移動において、自己交差は主に次の3つのパターンで発生します。

• パターン1： 4本目の移動が1本目の移動と交差するケース
• パターン2： 5本目の移動が1本目の移動と接触・交差するケース
• パターン3： 6本目の移動が4本目の移動と交差するケース

これらのパターンを効率よく検出するため、配列の先頭に 0 を番兵（ダミー値）として追加し、境界条件を統一的に扱えるようにします。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• 配列 x の先頭に 0 を4つ挿入する
• n := x のサイズ、i := 4 と初期化する
• i < n かつ x[i] > x[i - 2] が成り立つ間、i を1ずつ増やす（外側へ拡大していくスパイラル部分をスキップ）
• i が n と等しくなれば、交差は存在しないので false を返す
• x[i] >= x[i - 2] - x[i - 4] が成り立つ場合は、x[i - 1] = x[i - 1] - x[i - 3] として調整する
• i を1増やした後、i < n かつ x[i] < x[i - 2] が成り立つ間、i を1ずつ増やす（内側へ縮小していく部分をスキップ）
• 最後に、i が n と異なれば true を返す

このアルゴリズムは配列を一度だけ走査し、定数個の変数しか使用しないため、時間計算量 O(n)、空間計算量 O(1) という要件を満たしています。

実装例

理解を深めるために、C++での実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool isSelfCrossing(vector<int>& x) {
        x.insert(x.begin(), 4, 0);
        int n = x.size();
        int i = 4;
        for(; i < n && x[i] > x[i - 2]; i++);
        if(i == n) return false;
        if (x[i] >= x[i - 2] - x[i - 4]) {
            x[i - 1] -= x[i - 3];
        }
        for (i++; i < n && x[i] < x[i - 2]; i++);
        return i != n;
    }
};
main() {
    Solution ob;
    vector<int> v = {3,4,2,5};
    cout << (ob.isSelfCrossing(v));
}

入力

{3,4,2,5}

出力

1

出力が 1（true）となり、配列 {3, 4, 2, 5} に沿って移動した経路が自分自身と交差することが正しく判定されました。