概要

「現在いるマス」に加えて「次に移動する方向」を状態として管理し、幅優先探索（BFS）で最小移動回数を求めます。最初は縦・横のどちらにも移動できるため、始点には両方の状態を用意します。

考察

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

通常の迷路の最短経路問題では、各マスを訪問済みにする BFS が使えます。しかし、この問題では同じマスにいても、次に移動できる方向が異なる場合があります。

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

このため、マス単位で訪問済みにしてしまうと、次に移動できる方向が異なる経路まで探索対象から除外し、正しい答えを求められないことがあります。

「次に移動する方向」を状態に加える

そこで、次のように状態を定義します。

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

縦方向へ移動すると次は横方向、横方向へ移動すると次は縦方向になるので、移動するたびに状態の末尾の値を切り替えます。

各マスにつき状態は \(2\) 個なので、全体の状態数は最大 \(2HW\) 個です。

移動経路をすべて列挙する方法では、同じマスへの再訪も許されるため、探索が際限なく続く可能性があります。しかし、同じ「マスと次の方向」の状態に戻ったなら、その後にできる移動は同じです。したがって、各状態を最短で到達したときに一度だけ処理すれば十分です。

すべての移動のコストが同じなので BFS を使う

どの移動も移動回数を \(1\) 増やします。このようなグラフでは、BFS によって移動回数の少ない状態から順に探索できます。

最初の移動方向は自由なので、始点の \(2\) 状態

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

を、どちらも距離 \(0\) として探索を始めます。

アルゴリズム

1. 各空きマスについて、「次は縦方向」「次は横方向」の \(2\) 状態を用意します。
2. 始点の \(2\) 状態を訪問済みにし、キューに入れます。現在の移動回数を \(0\) とします。
3. キューから状態を取り出し、次の処理を行います。
   • 現在位置がゴールなら、現在の移動回数を出力して終了します。
   • 次が縦方向なら、上下のマスを調べます。
     • 移動先が空きマスで、「次は横方向」の状態が未訪問なら、訪問済みにしてキューに入れます。
   • 次が横方向なら、左右のマスを調べます。
     • 移動先が空きマスで、「次は縦方向」の状態が未訪問なら、訪問済みにしてキューに入れます。
4. 同じ移動回数の状態をすべて処理したら、移動回数を \(1\) 増やします。
5. ゴールに到達せずにキューが空になった場合は、NONE を出力します。

正しさ

状態遷移では、指定された方向にだけ移動し、その後で次の方向を切り替えています。そのため、探索で得られる経路は必ず縦・横の交互移動という条件を満たします。

逆に、条件を満たす移動は、この状態遷移としてすべて表せます。また、始点の両方の状態から探索するため、最初に縦へ動く経路も横へ動く経路も調べられます。

BFS は移動回数の小さい順に状態を取り出すので、初めてゴールの状態を取り出したときの移動回数が最小値です。探索を終えてもゴールが見つからなければ、到達する経路は存在しません。

計算量

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

状態数は最大 \(2HW\) 個で、各状態から調べる移動先は最大 \(2\) 個です。各状態は一度しかキューに入れないため、全体で \(O(HW)\) 時間となります。

実装のポイント

盤面の周囲に番兵を置く

コードでは、盤面の周囲を進入不可のマスで囲み、\((H+2)\times(W+2)\) の配列を使っています。

横幅を stride = W + 2 とすると、マス \((i,j)\) の一次元配列上の位置は

\(pos=i\cdot \mathrm{stride}+j\)

です。上下左右の位置は、それぞれ次のように求められます。

• 上：pos - stride
• 下：pos + stride
• 左：pos - 1
• 右：pos + 1

周囲の番兵は常に進入不可なので、移動先が盤面の範囲内かを毎回判定する必要がありません。

進入可能かどうかと訪問済み情報をまとめる

コード中の vertical と horizontal は、次の意味を持つ bytearray です。

• vertical[pos] == 1：空きマスであり、「次は縦方向」の状態が未訪問
• horizontal[pos] == 1：空きマスであり、「次は横方向」の状態が未訪問

障害物・番兵・訪問済み状態はいずれも 0 にします。キューに追加する時点で 0 にすることで、同じ状態の重複追加を防ぎます。

状態を整数 \(1\) 個で表す

位置を pos、次の方向を d として、状態を

(pos << 1) | d

で表しています。d = 0 が縦方向、d = 1 が横方向です。

取り出すときは、state >> 1 で位置を、state & 1 で方向を取得できます。

BFS を移動回数ごとに処理する

for _ in range(len(queue)) により、その時点でキューにある状態だけを処理します。処理中に追加された状態は次の周回に回るため、周回ごとに distance を \(1\) 増やすだけで移動回数を管理できます。

ソースコード

import sys
from collections import deque


def main():
    input = sys.stdin.buffer.readline
    H, W = map(int, input().split())

    stride = W + 2
    size = (H + 2) * stride
    vertical = bytearray(size)

    for i in range(1, H + 1):
        start = i * stride + 1
        vertical[start:start + W] = bytearray(
            x == b'0' for x in input().split()
        )

    horizontal = vertical[:]
    start = stride + 1
    goal = H * stride + W

    vertical[start] = 0
    horizontal[start] = 0

    queue = deque((start << 1, (start << 1) | 1))
    append = queue.append
    popleft = queue.popleft
    distance = 0

    while queue:
        for _ in range(len(queue)):
            state = popleft()
            pos = state >> 1

            if pos == goal:
                print(distance)
                return

            if state & 1:
                nxt = pos - 1
                if vertical[nxt]:
                    vertical[nxt] = 0
                    append(nxt << 1)

                nxt = pos + 1
                if vertical[nxt]:
                    vertical[nxt] = 0
                    append(nxt << 1)
            else:
                nxt = pos - stride
                if horizontal[nxt]:
                    horizontal[nxt] = 0
                    append((nxt << 1) | 1)

                nxt = pos + stride
                if horizontal[nxt]:
                    horizontal[nxt] = 0
                    append((nxt << 1) | 1)

        distance += 1

    print("NONE")


if __name__ == "__main__":
    main()

---

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