pudding

2 secs 1024 MB

解説

盤面上の「壁 # とプリン P」の総数は高々 $10$ 。
よって、現在位置と特殊マス（壁・プリン）の状態を合わせて幅優先探索（BFS）を行えば、最短ターン数が求まる。

状態： $(r, c, \mathrm{mask})$
ここで $r,c$ は現在位置、 $\mathrm{mask}$ は「特殊マスが処理済みかどうか」を表すビット集合（1 = 壁は破壊済み／プリンは取得済み）。
遷移は 1 手コストで 8 種類（移動4＋ブレス4）。BFS で最短手数を得る。

ポイントは ブレスの判定・更新を $O(1)$ に落とす前計算と、プリンの即失敗条件の扱いである。

ブレスは「選んだ方向の距離 $t=1,\dots,K$ の各マスを空マスに変える」操作であり、壁で遮られない（直線上すべてを見る）。
未取得のプリンを 1 つでも空マスに変えるブレスは不許可（即失敗）。
したがって、状態 $(r,c,\mathrm{mask})$ で方向 $d$ にブレスできるかは、
「その直線上に残っているプリンが無いか」を $\mathrm{mask}$ を用いて一括判定すればよい。
壁・プリンは合計で高々 $10$ 個なので、全特殊マスに 0.. $m-1$ のIDを付与してビット化できる。

特殊マス数を $m(\le 10)$ とし、各特殊マスに ID を付与。
位置 $(r,c)$ の特殊マスの ID を $id(r,c)$ と書く（該当しなければ $-1$ ）。
ビット集合 $\mathrm{mask}\in [0,2^m)$ $mask \in [0, 2^{m})$ を「処理済み集合」とする。
- 壁 #：破壊済みならそのビットを $1$ 。
- プリン P：取得済みならそのビットを $1$ 。
プリン集合ビットを $P_{\mathrm{bits}}$ として事前に作っておく。
クリア条件は $(\mathrm{mask}\ \&\ P_{\mathrm{bits}}) = P_{\mathrm{bits}}$ 。

初期状態は $(1,1,\ 0)$ （問題文の 1-index を 0-index に直す実装も可）。 $(1,1)$ は必ず .。

次マス $(r',c')$ が盤外なら不可。
次マスが壁 # かつ $id(r',c')=x$ のビットが $\mathrm{mask}$ 内で $0$ （未破壊）なら不可。
次マスがプリン P かつ $id(r',c')=y$ のビットが $\mathrm{mask}$ 内で $0$ （未取得）なら、
遷移先は $\mathrm{mask'}=\mathrm{mask}\ |\ (1\ll y)$ 。それ以外は $\mathrm{mask'}=\mathrm{mask}$ 。
手数は常に $+1$ 。

$(r,c)$ から方向 $d$ へ距離 $1\ldots K$ の直線上の 特殊マスのビット集合を $L[r][c][d]$ として前計算しておく（後述）。
未取得プリン判定： $((\sim \mathrm{mask})\ \&\ L[r][c][d]\ \&\ P_{\mathrm{bits}})\neq 0$ なら 不許可。
許可される場合、 $\mathrm{mask'}=\mathrm{mask}\ |\ L[r][c][d]$ （壁ビットをまとめて立てる。取得済みプリン等はそのまま）。
位置は変化せず、手数は $+1$ 。

各セル $(u,v)$ と各方向 $d$ に対して、「 $(u,v)$ で方向 $d$ にブレスしたとき影響を受ける特殊マスの集合」 $L[u][v][d]$ を求める。
構築方法の一例：

各特殊マス（ID 付き） $(x,y)$ から、各方向 $d$ について「ブレスの起点側」へ距離 $t=1\ldots K$ だけ逆にたどる。
到達可能な起点 $(u,v)=(x - t\cdot d_r,\ y - t\cdot d_c)$ が盤内なら、 $L[u][v][d]$ にその特殊マスのビットを加える。
これで「その特殊マスは $(u,v)$ から方向 $d$ に距離 $\le K$ の直線上にある」ことがビットで表現できる。

これにより、ブレスの可否判定・更新は ビット演算 2 回で完結し、遷移あたり $O(1)$ になる。

状態数は高々 $H W \cdot 2^{m}\ (\le 1000 \cdot 2^{10} = 1{,}024{,}000)$ 。
各状態からの遷移は最大 8（移動4＋ブレス4）。
ブレスの可否判定・更新は前計算により $O(1)$ 。
したがって全体の計算量 $O(HW\cdot 2^{m})$ で十分高速に動作する。

実装例は以下のようになります。