第14回日本情報オリンピック　予選５

2014年12月14日
情報オリンピック日本委員会

解説

部分点解法

すべてのマスを調べて崩れるかどうか判定する，という動作を繰り返す．崩れる城マスが一つも無くなったら終了．

計算量は O( (答え) × HW) となる．サンプル入力２を見ればわかるとおり，答えは HW 程度の大きさになりうる．そのため計算量は O(H^2W^2) となり，入力１では間に合うが，入力２以降は現実的な時間内に計算が終わらない．

満点解法

次の事実に注目しよう．二回目以降の波においては，崩れる城マスの候補は，前回の波で崩れたマスの周囲８マスにあるものに限られる．そのため，そのようなマスについてのみ崩れるかどうか判定すればよい．

このような方針で計算すると，任意の城マスについて，それが崩れるかどうかの判定は高々８回しか行われないことになる．そのため計算量は O(HW) となり，すべての入力に対して現実的な時間内に計算が終了する．

実装では，各波に対して，それによって崩れる城マスの位置をキューやスタックといったデータ構造に格納して記録すればよい．直前のひとつの波についてのみ記録しておけばよいので，次のようにすれば，用いるキューは実は二つで足りる．

• 二つのキューのうち片方にはある波で崩れた城マスの位置が格納されている．もう片方は空である．
• 前者のキューから要素をひとつ取り出す．その周囲８マスについて次の波で崩れるか否かを判定し，崩れるマスについては後者のキューにその位置を格納する． 前者のキューが空になるまでこれを繰り返すと，後者のキューには次の波で崩れる城マスの位置がすべて格納された状態になる．
• 二つのキューの役割を入れ替え，初めに戻る．

また，各マスについて，周囲の更地マスの数を記録し，あるマスが崩壊するたびに更新していくようにすれば，崩れるかどうかの判定が楽になる．