ABC472 D - Bomber Mad
爆破狂
考え方
やや特殊な迷路問題。
とはいえやることは単純で、以下を順に実行すればよい。
- 全てのマスを見て、爆弾が $1$ つも存在しない安全な行と列を列挙する
- 全てのマスを見て、行も列も安全なら、そこを安全マスとして記録する
- 安全マス全てを始点とする多始点幅優先探索で、各マスから最寄りの安全マスまでの距離を求める
- 全てのマスを見て、最寄りの安全マスまでの距離が $K$ 以下であるマスの数を愚直に数える
安全マスを求めるのに、毎回縦横のマスをチェックすると $O(HW(H+W))$ かかってしまう。
$1$ つめと $2$ つめを別作業にして計算量を $O(HW)$ にするのがポイント。
そこさえ気づければ、あとは実装力勝負。
全体の計算量は $O(HW)$ である。
入力例3での動作
入力を受け取る。
h: 5
w: 7
k: 2
s:
"..#...."
"..#...."
"......."
"...#..."
"...#..."爆弾が存在しない行は $3$ 行目だけである。
爆弾が存在しない列は $1,2,5,6,7$ 列目である。
したがって、安全マスは $(3,1),(3,2),(3,5),(3,6),(3,7)$ の $5$ マスとなる。
この $5$ マスを全て距離 $0$ として多始点幅優先探索を行う。
各マスから最寄りの安全マスまでの距離は次のようになる。# は爆弾マスである。
| $1$ 列 | $2$ 列 | $3$ 列 | $4$ 列 | $5$ 列 | $6$ 列 | $7$ 列 | |
|---|---|---|---|---|---|---|---|
| $1$ 行 | $2$ | $2$ | # |
$3$ | $2$ | $2$ | $2$ |
| $2$ 行 | $1$ | $1$ | # |
$2$ | $1$ | $1$ | $1$ |
| $3$ 行 | $0$ | $0$ | $1$ | $1$ | $0$ | $0$ | $0$ |
| $4$ 行 | $1$ | $1$ | $2$ | # |
$1$ | $1$ | $1$ |
| $5$ 行 | $2$ | $2$ | $3$ | # |
$2$ | $2$ | $2$ |
空マスは全部で $31$ マスあり、このうち距離が $2$ 以下なのは $(1,4)$ と $(5,3)$ 以外の全てである。
したがって、条件を満たすマスは $29$ マスである。
注意点
特になし。
別解
特になし。