AtCoder Beginner Contest 039

D - 画像処理高橋君


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

問題文

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

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

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

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

制約

  • 1 ≦ H, W ≦ 100
  • S_iW 文字の .# からなる文字列である

入力

入力は以下の形式で標準入力から与えられる。

H W
S_1
S_2
:
S_H

出力

もし条件を満たす画像が無いならば 1 行に impossible と出力する。

条件を満たす画像があるならば 1 行に possibleと出力したあと、W 文字の .# からなる文字列を H 行出力する。

i 行目の文字列の j 番目の文字は、条件を満たす画像の上から i 個目、左から j 個目の画素の色が白なら .、黒なら # とすること。


入力例1

4 4
##..
##..
..##
..##

出力例1

possible
#...
....
....
...#

入力例2

4 4
###.
####
..##
..##

出力例2

possible
##..
....
...#
...#

入力例3

4 4
###.
##.#
..##
..##

出力例3

impossible

Submit提出する