概要

\(H \times W\) のグリッド上で、縦方向の移動と横方向の移動を交互に行うロボットが \((1,1)\) から \((H,W)\) へ到達できるか判定し、可能なら最小移動回数を求める問題です。「次に縦へ動くのか横へ動くのか」という情報を状態に加えた拡張グリッド上の幅優先探索 (BFS) で解きます。

考察

まず素朴に考えてみる

通常の「障害物のあるグリッドの最短経路」なら、マス \((i,j)\) を頂点として BFS すれば \(O(HW)\) で解けます。しかし本問には「縦・横を交互に動く」という制約があります。

ここで、単に \((i,j)\) だけを状態として BFS してしまうとWA になります。なぜなら、同じマス \((i,j)\) に来ていても

• 「直前に縦へ動いたので、次は横に動かなければならない」状態
• 「直前に横へ動いたので、次は縦に動かなければならない」状態

の \(2\) 通りがあり、その後にできる動きが全く違うからです。一度 \((i,j)\) を訪問済みにしてしまうと、もう一方の状態で \((i,j)\) に来る経路を切り捨ててしまい、本来到達できるはずのゴールを見逃したり、最短でない答えを出したりします。

具体例

0 0
1 0

\(H=W=2\)。\((1,1)\) から \((1,2)\) へ横移動（1回目）、次は縦に動かなければならないので \((2,2)\) へ縦移動（2回目）。答えは \(2\)。

一方、

0 1
0 0

なら \((1,1) \to (2,1)\)（縦）\(\to (2,2)\)（横）で \(2\)。

しかし例えば

0 0 0
0 1 0
0 0 0

のような場合、真ん中を通れないため、経路によっては「縦・縦」と続けたくなる場面が出てきます。このとき同じマスに「次は縦」「次は横」の両方の状態で到達しうるので、状態を分けて管理する必要があるのです。

解決策：状態を拡張する

そこで、頂点を

\[(i,\ j,\ t) \quad (t \in \{0, 1\})\]

とします。ここで - \(t = 0\)：次の移動は縦方向でなければならない（＝直前は横に動いた、または最初の1手目） - \(t = 1\)：次の移動は横方向でなければならない（＝直前は縦に動いた、または最初の1手目）

遷移は次のようになります。

• \((i,j,0) \to (i\pm1,\ j,\ 1)\)（縦に動くと、次は横になる）
• \((i,j,1) \to (i,\ j\pm1,\ 0)\)（横に動くと、次は縦になる）

もちろん、移動先はグリッド内かつ \(A = 0\)（空きマス）である必要があります。

1回目の移動はどちらでもよいので、スタートは \((0,0,0)\) と \((0,0,1)\) の両方を距離 \(0\) で初期化します。ゴールは \((H-1,W-1,0)\) と \((H-1,W-1,1)\) のどちらかに到達すればよいので、両者の距離の最小値を取ります（0-indexed で書いています）。

すべての辺の重みが \(1\) なので、この拡張グラフ上で BFS すれば最短距離が求まります。

アルゴリズム

1. 頂点数 \(2HW\) の状態空間 \((i, j, t)\) を用意し、dist 配列を \(\infty\)（未訪問）で初期化。
2. dist[(0,0,0)] = dist[(0,0,1)] = 0 としてキューに両方を入れる。
3. キューから状態 \((i,j,t)\) を取り出し、
   • \(t = 0\) なら上下 \(2\) 方向へ、\(t = 1\) なら左右 \(2\) 方向へ遷移を試す。
   • 範囲内かつ空きマスで、遷移先が未訪問なら距離 \(+1\) を記録してキューに追加。
4. 終了後、min(dist[(H-1,W-1,0)], dist[(H-1,W-1,1)]) が答え。両方 \(\infty\) なら NONE を出力。

BFS は「先に訪問した方が必ず距離が短い（あるいは同じ）」という性質があるため、一度距離を確定したら二度更新しません。これで各状態は \(1\) 回だけ処理されます。

なお、\((i+j)\) の偶奇と \(t\) の間に関係があるため実は \(2HW\) 個の状態のうち有効なのは半分程度ですが、そこを気にせず単純に \(2\) 倍の状態を持って BFS すれば十分間に合います。

計算量

• 時間計算量: \(O(HW)\) — 状態数 \(2HW\)、各状態から出る辺は \(2\) 本なので \(O(HW)\)。\(H, W \le 1000\) より最大でも \(2 \times 10^6\) 状態程度。
• 空間計算量: \(O(HW)\) — dist 配列とグリッドで \(O(HW)\)。

実装のポイント

• 状態のエンコード：\((i,j,t)\) を 1 次元の整数 ((i*W + j)*2 + t) にまとめると、vector<int> 一本で距離を管理でき高速です。取り出すときは t = cur & 1、cell = cur >> 1、i = cell / W、j = cell % W で復元できます。

• スタートの初期化を忘れない：1 手目は縦横自由なので、\(t=0\) と \(t=1\) の両方をキューに入れます。片方だけにすると WA になります。

• ゴール判定：ゴールに着いた時点で「次にどちらへ動くべきか」は関係ないので、\(t=0,1\) 両方の距離の最小値を取ります。

• 到達不能の扱い：INF のままなら NONE を出力。\(H, W \le 1000\) で最大 \(10^6\) マスあるので、入力の読み込みは scanf や高速入力を使うと安心です（Python なら sys.stdin 一括読み込み）。

• BFS なので deque（または queue）を使い、重み付き最短路（ダイクストラ）は不要です。すべての辺の重みが \(1\) だからです。

  ソースコード

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

int main(){
    int H, W;
    if(scanf("%d %d", &H, &W)!=2) return 0;
    vector<vector<int>> A(H, vector<int>(W));
    for(int i=0;i<H;i++)for(int j=0;j<W;j++) scanf("%d", &A[i][j]);

    // state: (i,j,t) t=0 -> next move must be vertical, t=1 -> next move must be horizontal
    const int INF = INT_MAX;
    vector<int> dist((size_t)H*W*2, INF);
    auto idx=[&](int i,int j,int t){ return ((size_t)i*W + j)*2 + t; };

    deque<int> q;
    // start: at (0,0), first move can be either direction
    dist[idx(0,0,0)] = 0;
    dist[idx(0,0,1)] = 0;
    q.push_back((int)idx(0,0,0));
    q.push_back((int)idx(0,0,1));

    while(!q.empty()){
        int cur = q.front(); q.pop_front();
        int t = cur & 1;
        int cell = cur >> 1;
        int i = cell / W, j = cell % W;
        int d = dist[cur];
        if(t==0){
            // vertical move
            for(int di : {-1, 1}){
                int ni = i + di, nj = j;
                if(ni<0||ni>=H) continue;
                if(A[ni][nj]) continue;
                size_t ns = idx(ni,nj,1);
                if(dist[ns]==INF){ dist[ns]=d+1; q.push_back((int)ns); }
            }
        } else {
            for(int dj : {-1, 1}){
                int ni = i, nj = j + dj;
                if(nj<0||nj>=W) continue;
                if(A[ni][nj]) continue;
                size_t ns = idx(ni,nj,0);
                if(dist[ns]==INF){ dist[ns]=d+1; q.push_back((int)ns); }
            }
        }
    }

    int ans = INF;
    ans = min(dist[idx(H-1,W-1,0)], dist[idx(H-1,W-1,1)]);
    if(ans==INF) printf("NONE\n");
    else printf("%d\n", ans);
    return 0;
}

---

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