概要

マス目上を「縦移動」と「横移動」を交互に行いながら、スタートからゴールまでの最短手数を求める問題です。直前の移動方向を状態に含めて幅優先探索（BFS）を行うことで解くことができます。

考察

素朴なアプローチの問題点

通常の最短経路問題では「現在いるマス \((r, c)\)」のみを状態として管理し、訪問済みかどうかを記録します。 しかし本問では、「直前に縦に移動してきたか、横に移動してきたか」によって、次に進める方向（縦か横か）が制限されます。

そのため、単に「マス \((r, c)\) に到達した」という情報だけを記録していると、 - 「縦移動で到達したルート（次は横にしか動けない）」 - 「横移動で到達したルート（次は縦にしか動けない）」

が混同されてしまいます。例えば、あるマスに手数が同じで先に到達したルートがあっても、そのルートの向きのせいでゴールへ進めない場合、後から異なる向きで到達したルートを探索できずに誤った答え（WA）となってしまいます。

状態の拡張

この問題は、グラフの頂点（状態）を増やす「状態の拡張」によって解決できます。 ロボットの状態を以下のように \(3\) つ組で表します。

• \((r, c, \text{dir})\)
  • \(r, c\): 現在のマス（行番号、列番号）
  • \(\text{dir} = 0\): 直前に「縦移動」をした（次は「横移動」のみ可能）
  • \(\text{dir} = 1\): 直前に「横移動」をした（次は「縦移動」のみ可能）

このように状態を分けることで、同じマスであっても「縦から入ってきたか」「横から入ってきたか」を区別して最短手数を管理することができます。

アルゴリズム

すべての移動コストは \(1\) であるため、幅優先探索（BFS） を用いて最短手数を求めます。

1. 初期化:
   • 距離配列 dist[r][c][dir] を \(-1\) で初期化します。
   • スタート地点 \((1, 1)\) からの最初の \(1\) 手目は縦・横のどちらでもよいため、
     • 上または下に \(1\) マス進めるなら、そのマスを dist[nr][nc][0] = 1 としてキューに追加します。
     • 左または右に \(1\) マス進めるなら、そのマスを dist[nr][nc][1] = 1 としてキューに追加します。
2. BFS の遷移:
   • キューから状態 \((r, c, \text{dir})\) を取り出します。
   • 取り出したマスがゴール \((H, W)\) であれば、そのときの移動回数が最小値となります（BFS の性質より、最初に取り出された時点で最小手数が確定します）。
   • \(\text{dir} = 0\) の場合（次は横移動）：
     • 左右に隣接するマス \((r, c \pm 1)\) のうち、グリッド内で障害物のないマスへ移動します。
     • 未訪問（dist[r][nc][1] == -1）であれば距離を更新し、状態 \((r, nc, 1)\) をキューに追加します。
   • \(\text{dir} = 1\) の場合（次は縦移動）：
     • 上下に隣接するマス \((r \pm 1, c)\) のうち、グリッド内で障害物のないマスへ移動します。
     • 未訪問（dist[nr][c][0] == -1）であれば距離を更新し、状態 \((nr, c, 0)\) をキューに追加します。
3. 終了判定:
   • キューが空になるまでにゴールに到達できなかった場合は、到達不能であるため NONE を出力します。

計算量

• 時間計算量: \(O(HW)\)
  • 状態数は \(H \times W \times 2\) 通りです。各状態からの移動の候補は \(2\) 通り（縦なら上下、横なら左右）なので、探索する辺の総数は最大でも \(4HW\) 本です。\(H, W \le 1000\) より、状態数は最大で約 \(2 \times 10^6\) となり、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(HW)\)
  • 盤面の情報 \(A\)、距離配列 dist、BFS のキューを保持するために \(O(HW)\) のメモリを使用します。

実装のポイント

• 初手の扱い: スタート地点 \((1, 1)\) 自身を「向きを持たない特殊な状態」としてキューに入れるよりも、初手で進める隣接マスを距離 \(1\) としてあらかじめキューに入れておくことで、BFS ループ内の遷移を「縦なら横へ、横なら縦へ」というシンプルな反復だけに統一できます。

• 0-indexed の活用: プログラム内ではマス目の座標を \(0\) から \(H-1\)、\(0\) から \(W-1\) の 0-indexed で扱うと、境界値判定や配列の参照が簡潔になります。

  ソースコード

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

    int H, W;
    if (!(cin >> H >> W)) return 0;

    vector<vector<int>> A(H, vector<int>(W));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> A[i][j];
        }
    }

    // dist[r][c][dir]
    // dir = 0: 直前に縦移動した（次は横移動）
    // dir = 1: 直前に横移動した（次は縦移動）
    vector<vector<vector<int>>> dist(H, vector<vector<int>>(W, vector<int>(2, -1)));
    queue<pair<pair<int, int>, int>> q;

    // 縦方向の初手 (上または下)
    int dr[] = {-1, 1};
    for (int d = 0; d < 2; ++d) {
        int nr = 0 + dr[d];
        int nc = 0;
        if (nr >= 0 && nr < H && A[nr][nc] == 0) {
            dist[nr][nc][0] = 1;
            q.push({{nr, nc}, 0});
        }
    }

    // 横方向の初手 (左または右)
    int dc[] = {-1, 1};
    for (int d = 0; d < 2; ++d) {
        int nr = 0;
        int nc = 0 + dc[d];
        if (nc >= 0 && nc < W && A[nr][nc] == 0) {
            dist[nr][nc][1] = 1;
            q.push({{nr, nc}, 1});
        }
    }

    int ans = -1;

    while (!q.empty()) {
        auto [pos, dir] = q.front();
        q.pop();
        auto [r, c] = pos;

        if (r == H - 1 && c == W - 1) {
            ans = dist[r][c][dir];
            break;
        }

        int d = dist[r][c][dir];

        if (dir == 0) {
            // 次は横移動
            for (int i = 0; i < 2; ++i) {
                int nr = r;
                int nc = c + dc[i];
                if (nc >= 0 && nc < W && A[nr][nc] == 0) {
                    if (dist[nr][nc][1] == -1) {
                        dist[nr][nc][1] = d + 1;
                        q.push({{nr, nc}, 1});
                    }
                }
            }
        } else {
            // 次は縦移動
            for (int i = 0; i < 2; ++i) {
                int nr = r + dr[i];
                int nc = c;
                if (nr >= 0 && nr < H && A[nr][nc] == 0) {
                    if (dist[nr][nc][0] == -1) {
                        dist[nr][nc][0] = d + 1;
                        q.push({{nr, nc}, 0});
                    }
                }
            }
        }
    }

    if (ans != -1) {
        cout << ans << "\n";
    } else {
        cout << "NONE\n";
    }

    return 0;
}

---

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