概要

現在のマスに加えて「次に移動する方向の種類」を状態として持ち、幅優先探索（BFS）を行います。縦・横の交互移動を状態遷移で表すことで、最小移動回数を求められます。

考察

マスだけでは状態を区別できない

通常の迷路の最短経路なら、各マスまでの距離を BFS で求めれば十分です。しかし、この問題では、同じマスにいても直前の移動方向によって次に進めるマスが異なります。

例えば、あるマスへ上から到着した場合、次は左右にしか移動できません。一方、左から到着した場合、次は上下にしか移動できません。

したがって、マスごとに一度だけ訪問する通常の BFS では、必要な経路を探索せずに打ち切ってしまい、誤答になる可能性があります。

「次に移動する軸」を状態に追加する

状態を次のように定義します。

• \((i,j,0)\)：マス \((i,j)\) にいて、次は縦方向に移動する
• \((i,j,1)\)：マス \((i,j)\) にいて、次は横方向に移動する

このように分ければ、各状態から可能な移動が一意に決まります。

• 次が縦方向なら、上下の空きマスへ移動し、次の軸を横方向にする
• 次が横方向なら、左右の空きマスへ移動し、次の軸を縦方向にする

同じマスへの再訪も、次に移動する軸が異なれば別の状態として扱います。一方、同じマス・同じ軸の状態なら、その先でできることは同じなので、最短距離で一度到達すれば十分です。

最初の移動は両方を許す

最初は縦・横のどちらへ移動してもよいため、次の両方を距離 \(0\) の初期状態にします。

• \((1,1,0)\)
• \((1,1,1)\)

すべての移動のコストは \(1\) なので、この状態グラフを BFS で探索すれば最短距離が求まります。

アルゴリズム

1. 各状態までの最短距離を保存する配列 dist を、未訪問を表す -1 で初期化します。
2. 始点の「次が縦方向」「次が横方向」の両状態の距離を \(0\) にし、キューに入れます。
3. キューが空になるまで、先頭の状態を取り出して次を行います。
   • 現在のマスが \((H,W)\) なら、その状態の距離を出力して終了します。
   • 次に移動する軸に応じて、上下または左右の \(2\) マスを調べます。
   • 移動先がマス目の範囲内の空きマスなら、軸を反転させた状態を考えます。
   • その状態が未訪問なら、距離を「現在の距離 \(+1\)」にしてキューへ追加します。
4. ゴールに到達しないままキューが空になった場合は、NONE を出力します。

正しく最短距離を求められる理由

状態遷移では、指定された軸に沿って \(1\) マス移動し、そのたびに軸を反転させています。したがって、探索で得られる経路は必ず交互移動の条件を満たします。

逆に、条件を満たすロボットの移動は、どれもこの状態グラフ上の経路として表せます。最初の軸も両方用意しているため、有効な経路を漏らしません。

BFS は距離の小さい状態から順に取り出します。そのため、ゴールの状態を初めて取り出したときの距離が、すべての有効な経路の中で最小になります。

計算量

各マスにつき状態は \(2\) 個で、各状態から調べる移動先は高々 \(2\) 個です。各状態は一度だけキューに追加されます。

• 時間計算量: \(O(HW)\)
• 空間計算量: \(O(HW)\)

実装のポイント

外周を障害物で囲む

提示コードでは、元のマス目の周囲に幅 \(1\) の障害物を追加しています。

これにより、上下左右の移動先が範囲外かどうかを毎回判定せず、blocked[nextCell] だけで進入可能かを確認できます。外周には進入しないため、そのさらに外側を調べることもありません。

マスと状態を整数で管理する

外周を含む横幅を stride = W + 2 とし、マス \((i,j)\) を

\(cell = i \times stride + j\)

で表します。このとき、上下のマスは cell ± stride、左右のマスは cell ± 1 です。

さらに、状態を

\(state = 2 \times cell + axis\)

とすると、state / 2 でマス番号、state & 1 で次の軸を取り出せます。軸の切り替えは axis ^ 1 で行えます。

訪問済み判定はキューに追加するときに行う

次の状態をキューへ追加する時点で dist を設定します。こうすると、同じ状態が重複してキューへ入ることを防げます。

提示コードでは、vector<int> の末尾へ状態を追加し、添字 head を増やしながら読み出すことで、先入れ先出しのキューとして利用しています。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int H, W;
    cin >> H >> W;

    const int stride = W + 2;
    const int cells = (H + 2) * stride;
    vector<unsigned char> blocked(cells, 1);

    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            int a;
            cin >> a;
            blocked[i * stride + j] = static_cast<unsigned char>(a);
        }
    }

    const int start = stride + 1;
    const int goal = H * stride + W;

    // State: cell * 2 + next movement axis (0: vertical, 1: horizontal).
    vector<int> dist(cells * 2, -1);
    vector<int> que;
    que.reserve(2 * H * W);

    for (int axis = 0; axis < 2; ++axis) {
        int state = start * 2 + axis;
        dist[state] = 0;
        que.push_back(state);
    }

    for (size_t head = 0; head < que.size(); ++head) {
        int state = que[head];
        int cell = state / 2;
        int axis = state & 1;

        if (cell == goal) {
            cout << dist[state] << '\n';
            return 0;
        }

        int delta = (axis == 0 ? stride : 1);
        for (int nextCell : {cell - delta, cell + delta}) {
            if (blocked[nextCell]) continue;

            int nextState = nextCell * 2 + (axis ^ 1);
            if (dist[nextState] != -1) continue;

            dist[nextState] = dist[state] + 1;
            que.push_back(nextState);
        }
    }

    cout << "NONE\n";
    return 0;
}

---

この解説は gpt-6-astra-medium によって生成されました。