倉庫番最短経路探索（BFS）解説

倉庫番攻略ガイドでは、一部ステージを幅優先探索（BFS）の手法で最短経路に更新しています。
このページでは、BFSがどのようにして最短手数を求めているかを解説します。

- 例：STAGE 004 -

壁

床

ゴール

箱

プレイヤー

箱 4個ゴール 4個

BFS では各盤面を State としてハッシュマップに登録し、同じ盤面への再訪問を防ぎます。

プレイヤー Pos(r, c)

箱の位置配列 int[] boxes（ソート済み）

State{ player=Pos(3,2), boxes=[22, 24, 34, 37] }

箱の座標は行番号・列番号から計算した1次元の整数に変換してソート保持しています。これにより同じ盤面かどうかを高速に判定できます。

static int posToInt(Pos p, int width) {
    return p.r * width + p.c;
    // 例: Pos(3,2), width=10 → 32
}

BFS は「キュー（待ち行列）」を使い、手数の少ない状態から順番に展開します。
最初にゴールへ到達した瞬間、それが最短経路です。

① 初期状態をキューに追加（手数=0）

↓

② キュー先頭の State を取り出す

↓

③ 全箱がゴール上？
Yes → 解答！　No → 続行

↓ No

④ U / D / L / R を試みる

↓

⑤ 未訪問の新 State をキューに追加

↓

② に戻る（キューが空になるまで）

キューの状態イメージ（色 = 手数）

State / 手数0 State / 手数1 State / 手数1 State / 手数1 State / 手数2 State / 手数2 State / 手数3 …

同じ手数の状態を全部処理してから次の手数へ進む → 最初に到達＝最短

箱があるときは「箱の先が空きかどうか」を確認します。壁や別の箱があれば押せません。

異なる手順で同じ盤面に到達することがあります。BFS では最初に到達した経路が最短なので、2回目以降はスキップします。

重複排除の効果
同じ盤面を何度も処理せず済むため、探索が大幅に高速化されます。

状態空間の爆発
重複排除なしでは同じ盤面を何度も処理してしまい、現実的な時間では解けません。

「次の手数を展開」を押すごとに、BFSが手数0→1→2…と状態を広げていく様子を確認できます。盤面をクリックすると右に拡大表示します。
※ STAGE 004は最短114手のステージですが、手数が増えるにつれて状態数が爆発的に増加するため、ここでは手数4までを表示しています。

新しい状態への遷移

訪問済みへの遷移（スキップ）

選択中の盤面

盤面をクリックして詳細表示

各盤面は、そこへ至るまでの手順文字列（U / D / L / R の並び）も一緒に保持しています。ゴールに到達した瞬間、その文字列がそのまま最短経路の解答になります。

STAGE 004 の探索結果：最短 114手

※ 箱数が増えると探索すべき盤面数が急増します。箱7個のステージでは GCP Cloud Batch（メモリ約100GB）を使用しています。