日本情報オリンピック (JOI) 2014年 予選 5問目 砂の城 (Sandcastle)
※このエントリは競プロで圧倒的成長 Advent Calendar 2015の10日目のエントリです．
もうすぐJOIの予選らしくTLが盛り上がっている．
去年の過去問見たらなんとかいけるかという感じだったので解いてみた．
解法思いついたのはわりと早かったけど実装力がアレだった…
問題概要
- H * W のマスに更地と強度1~9の城がある．
- マスの外は更地である
- 1度，波が来ると周囲8マスの更地の数が強度以上の城を潰れる
- 波が来ても状態が変わらなくなるまで何度の波が来るか
解法
- 壊れた城の周り以外は更地の数が変化しないので無視できる
- 最初の1回だけ全マスをチェックし，次以降は壊れた城の周りの城のみをチェックする
- オーダーはHWくらい
出場される方は頑張ってください．
