AtCoder Beginner Contest 039 D - 画像処理高橋君

D - 画像処理高橋君

時間制限 : 2sec / メモリ制限 : 256MB

問題文

2 値画像に対して行う、収縮という処理があります。なお、2 値画像とは、画素の色が白か黒かの 2 種類しかない画像の事です。

収縮とは、それぞれの画素についてその画素と周り 8 方向の画素のうち、一つでも黒い画素があったらその画素を黒くするという処理です。

ここで、画素数が高さ H、幅 W の 2 値画像を考えます。この画像はある画像に一回収縮を行ったものであることがわかっています。元の画像として考えられるものがあるかを判定し、もしあるならばそのうちどれか 1 つを復元してください。

画像は、H 個の、W 文字の文字列 Si で与えられます。Si の j 文字目は、上から i 個目、左から j 個目の画素の色を表しており、. なら白、# なら黒です。

note

深さ優先するのかな？と思ったら、条件分岐を気をつけて、貪欲にやればよいだけでした。おしまい。