Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 295 B問題 Bombs

AtCoder ABC ABC295 200 pts B問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$R$ 行 $C$ 列からなるマス目がある. 上から $i$ 行目, 左から $j$ 列目のマス目を $(i,j)$ と書くことにする.

$(i,j)$ の状態は文字 $B_{i,j}$ で表され, それぞれ以下のような意味合いである.

$B_{i,j}={\tt .}$ ならば, マス $(i,j)$ は空きマスである.
$B_{i,j}={\tt \#}$ ならば, マス $(i,j)$ は壁である.
$B_{i,j}$ が数字ならば, マス $(i,j)$ には威力がその数字である爆弾がある.

マス目にある爆弾が全て同時に爆発する. ここで, マス $(x,y)$ にある威力 $P$ の爆弾が爆発すると, マス $(x,y)$ からマンハッタン距離が $P$ 以下であるマス目全てが空きマスに変わる.

爆発後, $R$ 行 $C$ 列のマス目の状態はどのようになっているか?

制約

$1 \leq R,C \leq 20$
$B_{i,j}$ は ${\tt \#}, {\tt .}, {\tt 1}, \dots, {\tt 9}$ のどれか

解法

各爆弾について, その爆弾によって影響を受けるマスを愚直に調べ, 影響を受けたマスを空きマスにすればよい. ただし, 空きマスにする際に, 爆弾があるマスは空きマスにしてはいけない.

計算量は $O(R^2 C^2)$ 時間である.