概要

\(H \times W\) のグリッド上で、縦移動と横移動を交互に行うロボットが \((1,1)\) から \((H,W)\) へ到達できるか判定し、可能なら最小移動回数を求める問題です。「マス + 直前の移動方向」を頂点とする状態グラフ上の幅優先探索（BFS）で解けます。

考察

素朴な BFS ではダメな理由

普通の最短経路問題なら「マス \((i,j)\)」を頂点として BFS すれば済みます。しかし本問では「次にどちらの方向へ動けるか」が直前の移動方向によって変わるため、同じマスにいても状況が異なります。

例えばマス \((2,2)\) にいるとき、 - 直前が縦移動だった場合 → 次は横（左右）にしか動けない - 直前が横移動だった場合 → 次は縦（上下）にしか動けない

つまり、マスの座標だけでは「そこから先にどう動けるか」が決まりません。座標のみを状態として BFS すると、本来行けない遷移を許してしまったり（WA）、逆に先に到達した状態で上書きしてしまって最適解を見逃したりします。

解決法：状態を拡張する

そこで、頂点を

\[(\text{マスの位置},\ \text{直前の移動方向のタイプ})\]

というペアに拡張します。方向タイプは「縦」「横」の \(2\) 種類だけなので、頂点数は \(2HW\) 個です。

• 状態 \((\,(i,j),\ \text{縦}\,)\)：直前に縦移動した状態 → 次は左右へのみ遷移可能
• 状態 \((\,(i,j),\ \text{横}\,)\)：直前に横移動した状態 → 次は上下へのみ遷移可能

すべての辺の重みが \(1\)（1 回の移動 = コスト 1）なので、BFS で最短距離が求まります。

始点と終点の扱い

• 始点：1 回目の移動は縦・横どちらでもよいので、\((\,(1,1),\text{縦}\,)\) と \((\,(1,1),\text{横}\,)\) の両方を距離 \(0\) として BFS のキューに入れます（「直前が縦だった」と仮定した状態から始めれば次は横へ動ける、というように解釈します）。
• 終点：\((H,W)\) に着いたときの直前方向は縦でも横でもよいので、\((\,(H,W),\text{縦}\,)\) と \((\,(H,W),\text{横}\,)\) の距離の小さい方が答えです。両方とも未訪問なら NONE を出力します。

なお「同じマスを複数回訪れてよい」という条件がありますが、状態拡張済みグラフでは各状態を一度訪問すればよいので、特別な処理は不要です（同じマスでも方向タイプが違えば別頂点なので、最大 2 回まで訪れる余地があります）。

アルゴリズム

1. グリッドを 1 次元配列 g として読み込む（マス \((i,j)\) は添字 \( (i-1)W + (j-1) \)）。
2. 距離配列 dist を長さ \(2HW\) で用意し、すべて \(-1\)（未訪問）で初期化。
   • 添字 \(u < HW\)：マス \(u\) にいて直前が縦移動（次は横へ動く）
   • 添字 \(u \ge HW\)：マス \(u - HW\) にいて直前が横移動（次は縦へ動く）
3. dist[0] = 0, dist[HW] = 0 として、この 2 頂点をキューに入れる。
4. BFS を回す。
   • 状態が「次は横」なら、左 \((u-1)\) と右 \((u+1)\) の隣接マスへ。移動先の状態タイプは「横」になる。
   • 状態が「次は縦」なら、上 \((u-W)\) と下 \((u+W)\) の隣接マスへ。移動先の状態タイプは「縦」になる。
   • 移動先が範囲内かつ障害物でなく、未訪問なら距離を更新してキューに追加。
5. 目標マス \(HW-1\) にどちらかの状態で到達したら、その距離が答え（BFS なので最初に到達したときが最小）。到達できなければ NONE。

計算量

頂点数 \(2HW \le 2 \times 10^6\)、各頂点の出次数は \(2\) なので辺数も \(O(HW)\) です。

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

実装のポイント

• 1 次元配列化：\(H, W \le 1000\) で最大 \(10^6\) マス、状態数は \(2 \times 10^6\) です。2 次元リストのリストにすると Python では重いので、dist は長さ \(2HW\) の 1 次元リスト、グリッドは bytearray にすると高速かつ省メモリです。

• 左右移動の境界チェック：1 次元化すると、添字 \(u\) の列は u % W です。u % W == 0 のとき左端なので左へ行けず、u % W == W-1 のとき右端なので右へ行けません。ここを忘れると行をまたいでワープするバグになります（上下移動は u - W >= 0、u + W < N のチェックだけで済みます）。

• 入力の高速読み込み：\(10^6\) 個の数値を読むので、sys.stdin.buffer.read().split() で一括読み込みし、int() 変換すら省いてバイト列 b'1' と直接比較すると高速です。

• キューは collections.deque でも良いですが、リスト + head インデックス方式（q.append と head += 1）でも十分に速く、本コードではこれを使っています。

• 早期終了：目標マスに初めて到達した時点で BFS を打ち切ってよいです。ただし打ち切らなかった場合に備え、最後に \((H,W)\) の 2 つの状態の距離の min を取る処理も用意しておくと安全です。

• 答えの下限：\((1,1)\) から \((H,W)\) への移動回数は最低 \((H-1)+(W-1)\) 回ですが、交互制約により余分に往復が必要になるケースがあるため、単純な式では求まりません。必ず BFS で求めましょう。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    H = int(data[0]); W = int(data[1])
    N = H * W
    g = bytearray(N)
    i = 0
    off = 2
    for k in range(N):
        if data[off + k] == b'1':
            g[k] = 1
    dist = [-1] * (2 * N)
    target = N - 1
    dist[0] = 0
    dist[N] = 0
    q = [0, N]
    head = 0
    ans = -1
    while head < len(q):
        u = q[head]; head += 1
        du = dist[u] + 1
        if u < N:
            # last move vertical -> now horizontal
            j = u % W
            if j:
                v = u - 1
                if g[v] == 0:
                    w = N + v
                    if dist[w] < 0:
                        dist[w] = du
                        if v == target:
                            ans = du
                            break
                        q.append(w)
            if j + 1 < W:
                v = u + 1
                if g[v] == 0:
                    w = N + v
                    if dist[w] < 0:
                        dist[w] = du
                        if v == target:
                            ans = du
                            break
                        q.append(w)
        else:
            c = u - N
            # last move horizontal -> now vertical
            if c >= W:
                v = c - W
                if g[v] == 0:
                    if dist[v] < 0:
                        dist[v] = du
                        if v == target:
                            ans = du
                            break
                        q.append(v)
            v = c + W
            if v < N:
                if g[v] == 0:
                    if dist[v] < 0:
                        dist[v] = du
                        if v == target:
                            ans = du
                            break
                        q.append(v)
    if ans < 0:
        d1 = dist[target]
        d2 = dist[N + target]
        if d1 < 0 and d2 < 0:
            sys.stdout.write("NONE\n")
            return
        if d1 < 0:
            ans = d2
        elif d2 < 0:
            ans = d1
        else:
            ans = d1 if d1 < d2 else d2
    sys.stdout.write(str(ans) + "\n")

main()

---

この解説は claude5opus-high によって生成されました。