概要
色々な解法が考えられますが，基本的には問題の内容をきちんと実装すれば解くことができます．
問題原案：@uni_kakurenbo
解説
幅優先探索
例によってアルゴリズム自体の詳細な解説は他サイト様へ委ねます．
実装例-1 [C++]
しかし，幅優先探索を知らなくても，次のように実装することでこの問題は解けます．
本質は幅優先探索に変わりありません．
(詳細はコメントを参照してください．)
実装例-2 [C++]
Union-Find
Union-Find というデータ構造を用いることでも正答することができます． こちらも，データ構造自体の詳細な解説は他サイト様へ委ねます．
一度爆発したものを再度カウントしてしまわないように注意しましょう．
想定解-3 [C++]
発展
ボーナス問題 - ありがちな出題パターン
- 「 番目の爆発物が誘爆を引き起こす範囲の半径を として同じ問題をとけ．」
- 「最後に爆破される爆発物の番号と，最後の爆破が起こる時刻を求めよ．」
- 上記二つの複合
- etc...
類題
(難易度順)
実装例
上記を参照してください．
余談
Ex を見て真っ先に Explosion という単語を入れようと決意しました．
結果的にいつぞやの D に似てしまいましたがご容赦を..