C - Snuke the Cookie Picker Editorial by pointN


.のマスであって、上下左右にある#の数が2以上であるような場所が答えです。計算量は\(O(HW)\)です。

理由

上下左右に隣接するマスの#の数に注目します。すぬけ君がクッキーを食べる前、クッキーがあるマスでは、この数は2以上です(角の部分では2、辺の部分では3、内側は4)。いっぽう、クッキーがない場所では、この値は高々1です(クッキーのある長方形に隣接している部分では1、それ以外は0)。すぬけ君がクッキーを食べた後、そのマスは#から.になりますが、隣接する#の数は変わりません。また、もとから.であった場所で、隣接する#の数が増えることもありません。結局、上に書いた条件を満たすのは、すぬけ君がクッキーを食べた場所だけです。

posted:
last update: