C++で迷路からの脱出可否を判定するアルゴリズムと実装例

問題の概要

この問題では、n個の整数で構成される迷路が与えられます。各整数はそのマスから何マス移動するかを表し、移動の向きは「>」(右方向)と「<」(左方向)の記号で示されます。開始地点はインデックス0の位置で、そこから迷路の外へ脱出できるかどうかを判定することが課題です。

入力例と出力例

具体例で問題の内容を確認してみましょう。

入力: 移動距離の配列 arr[] = {2, 1, 1, 4}、方向の並び s = "><>>"

出力: YES

説明: スタート地点から右へ2マス進み(インデックス2)、さらに右へ1マス(インデックス3)、そして右へ4マス進むことで、迷路の範囲(インデックス0〜3)の外へ出ることができます。

解決アプローチ

この問題は、移動を実際にシミュレーションすることで解けます。脱出の条件は、現在位置が0未満(左側の外)またはn以上(右側の外)になることです。

具体的には、開始地点のインデックス0から出発し、現在位置の記号(> または <)が示す向きへ、そのマスに書かれた整数の数だけ移動します。これを繰り返し、迷路の外に到達できれば「脱出可能」と判定します。

無限ループの検出

もう一つ考慮すべき重要なケースが「無限ループ」です。移動を続けるうちに、以前に訪れた位置へ戻ってしまうと、以後は同じ経路を永遠に周回し続けることになり、二度と迷路から出られなくなります。

そこで、訪問済みのマスすべてにマークを付けておきます。移動先がすでにマークされている場合は、ループに陥ったと判断して探索を打ち切り、「永遠に迷路から出られない」という結果を出力します。この工夫により、プログラムが無限に停止しなくなる事態を防げます。

C++による実装例

以上の考え方を実装したプログラムが以下です。

#include <iostream>
#include <vector>
using namespace std;

void isMazeSolvable(int a[], int n, string s) {
    vector<int> mark(n, 0); // 訪問済みマーク
    int start = 0;
    bool possible = true;
    while (start >= 0 && start < n) {
        if (mark[start] == 1) { // 訪問済みなら無限ループ
            possible = false;
            break;
        }
        mark[start] = 1;
        if (s[start] == '<')
            start -= a[start];
        else
            start += a[start];
    }
    if (!possible)
        cout << "It stays inside the maze forever";
    else
        cout << "It will come out of the maze";
}

int main() {
    int n = 3;
    string s = ">><";
    int a[] = { 1, 2, 4 };
    isMazeSolvable(a, n, s);
    return 0;
}

実行結果

It will come out of the maze

このケースでは、インデックス0 → 1 → 3 と移動して n=3 の境界を越えるため、「It will come out of the maze(迷路から出ることができます)」と表示されます。もし途中で同じマスに戻ってしまった場合は、「It stays inside the maze forever(永遠に迷路の中にとどまります)」が出力されます。

計算量

• 時間計算量: O(n) — 各マスは高々1回しか訪問されないため
• 空間計算量: O(n) — 訪問済み判定用の配列が必要

まとめ

迷路脱出問題は、移動ルールに沿ってシミュレーションを行い、「迷路の外に出た」「すでに訪れた位置に戻ってきた」の2つの状態で結果を判定するシンプルなアルゴリズムです。訪問済みマークによって無限ループを確実に検出できる点が大きなポイントです。