概要

\(H \times W\) のグリッド上を、縦移動と横移動を交互に行いながら、スタート地点 \((1, 1)\) からゴール地点 \((H, W)\) までの最小移動回数を求める問題です。

考察

通常の最短経路問題との違い

通常のグリッド上の最短経路問題（幅優先探索: BFS）では、「現在どのマス \((r, c)\) にいるか」という情報だけで探索を行うことができます。 しかし本問では、「直前に縦移動したか、横移動したか」（言い換えると「次は縦と横のどちらに移動しなければならないか」）という制約があります。 そのため、同じマスにいる場合でも「次は縦にしか動けない状態」と「次は横にしか動けない状態」は全く異なる状況として区別する必要があります。

状態の拡張（拡張グラフ）

そこで、「現在のマス \((r, c)\)」に「次に移動できる方向 \(t\)」の情報を加えた 状態 を考えます。

• \(t = 0\): 次の移動は 横方向（左または右）
• \(t = 1\): 次の移動は 縦方向（上または下）

このように状態を拡張すると、各状態からの遷移は次のようになります。 - 状態 \(((r, c), t = 0)\) からは、左右の空きマス \((r, c \pm 1)\) へ移動し、遷移後の状態は \(((r, c \pm 1), t = 1)\) となる。 - 状態 \(((r, c), t = 1)\) からは、上下の空きマス \((r \pm 1, c)\) へ移動し、遷移後の状態は \(((r \pm 1, c), t = 0)\) となる。

すべての移動コストは \(1\) であるため、この拡張されたグラフ上で幅優先探索 (BFS) を行うことで、最小移動回数を求めることができます。

スタートとゴール

• スタート: 最初は縦・横どちらへ移動してもよいため、\(((1, 1), t = 0)\) と \(((1, 1), t = 1)\) の両方をコスト \(0\) の初期状態として探索を開始します。
• ゴール: 最終的に \((H, W)\) に到達できれば、そのときの \(t\)（直前の移動が縦か横か）はどちらでも構いません。

アルゴリズム

1. 各状態を「マスの番号 \(\text{idx} = r \times W + c\)」と「移動方向 \(t \in \{0, 1\}\)」の組で表します。
2. 最短距離を管理する配列 dist をサイズ \(2 \times H \times W\) で用意し、すべて \(-1\)（未訪問）で初期化します。
3. スタート地点の状態 \(((1, 1), 0)\) および \(((1, 1), 1)\) の距離を \(0\) とし、キューに追加します。
4. キューから状態を \(1\) つ取り出し、現在の \(t\) に応じて次のマスを探索します：
   • \(t = 0\) の場合: 左右に隣接するマスを調べる。空きマスかつ未訪問であれば、次の状態（\(t = 1\)）の距離を更新してキューに追加します。
   • \(t = 1\) の場合: 上下に隣接するマスを調べる。空きマスかつ未訪問であれば、次の状態（\(t = 0\)）の距離を更新してキューに追加します。
5. 探索の途中でマス \((H, W)\) に到達した時点で、そのときの移動回数を出力して終了します（幅優先探索の性質上、最初に到達した手数が最小となります）。
6. キューが空になってもマス \((H, W)\) に到達できなかった場合は NONE を出力します。

計算量

• 時間計算量: \(O(HW)\)
  • 状態数は頂点数 \(V = 2HW\) です。
  • 各頂点からの遷移（移動の選択肢）は高々 \(2\) 通りなので、辺数は \(E \leq 4HW\) です。
  • BFS の時間計算量は \(O(V + E) = O(HW)\) となり、制約 \(H, W \leq 1000\)（\(HW \leq 10^6\)）において十分高速に動作します。
• 空間計算量: \(O(HW)\)
  • 状態ごとの距離配列 dist や BFS のキューのサイズとして \(O(HW)\) のメモリを使用します。

実装のポイント

• 状態の数値化: マスのインデックス idx と方向 t を、ビット演算を用いて (idx << 1) | t とすることで \(1\) つの整数として管理できます。これにより配列アクセスが高速化され、メモリ使用量も抑えることができます。

• 早期終了: キューから取り出すタイミングではなく、次の移動先がマス \((H, W)\) であることを確認した瞬間に答えを出力して終了することで、余分な探索を省略できます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    H = int(input_data[0])
    W = int(input_data[1])
    
    grid = [int(x) for x in input_data[2:]]
    
    target_idx = H * W - 1
    total_states = 2 * H * W
    dist = [-1] * total_states
    
    # 状態: (idx << 1) | t
    # t = 0: 次の移動は横方向
    # t = 1: 次の移動は縦方向
    dist[0] = 0
    dist[1] = 0
    
    q = [0, 1]
    head = 0
    
    while head < len(q):
        u = q[head]
        head += 1
        
        d = dist[u]
        idx = u >> 1
        t = u & 1
        
        r = idx // W
        c = idx % W
        
        if t == 0:
            # 横移動
            if c > 0:
                nidx = idx - 1
                if grid[nidx] == 0:
                    nxt = (nidx << 1) | 1
                    if dist[nxt] == -1:
                        if nidx == target_idx:
                            print(d + 1)
                            return
                        dist[nxt] = d + 1
                        q.append(nxt)
            if c + 1 < W:
                nidx = idx + 1
                if grid[nidx] == 0:
                    nxt = (nidx << 1) | 1
                    if dist[nxt] == -1:
                        if nidx == target_idx:
                            print(d + 1)
                            return
                        dist[nxt] = d + 1
                        q.append(nxt)
        else:
            # 縦移動
            if r > 0:
                nidx = idx - W
                if grid[nidx] == 0:
                    nxt = (nidx << 1) | 0
                    if dist[nxt] == -1:
                        if nidx == target_idx:
                            print(d + 1)
                            return
                        dist[nxt] = d + 1
                        q.append(nxt)
            if r + 1 < H:
                nidx = idx + W
                if grid[nidx] == 0:
                    nxt = (nidx << 1) | 0
                    if dist[nxt] == -1:
                        if nidx == target_idx:
                            print(d + 1)
                            return
                        dist[nxt] = d + 1
                        q.append(nxt)
                        
    print("NONE")

if __name__ == '__main__':
    main()

---

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