C - Snuke the Cookie Picker Editorial by pointN
.
のマスであって、上下左右にある#
の数が2以上であるような場所が答えです。計算量は\(O(HW)\)です。
上下左右に隣接するマスの
posted:
理由
#
の数に注目します。すぬけ君がクッキーを食べる前、クッキーがあるマスでは、この数は2以上です(角の部分では2、辺の部分では3、内側は4)。いっぽう、クッキーがない場所では、この値は高々1です(クッキーのある長方形に隣接している部分では1、それ以外は0)。すぬけ君がクッキーを食べた後、そのマスは#
から.
になりますが、隣接する#
の数は変わりません。また、もとから.
であった場所で、隣接する#
の数が増えることもありません。結局、上に書いた条件を満たすのは、すぬけ君がクッキーを食べた場所だけです。
last update: