天下一プログラマーコンテスト2014予選B

C - 天下一王国の歴史


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

問題文

天下一王国の歴史を学んでいるトモアキ君は、王国を導いた偉大な英雄である HAGIXILE について調べています。

HAGIXILE は奇行で知られる人物でした。彼は王国の領土を N \times N のマスに分割された盤面とし、白マスと黒マスに分けて扱いました。

白マスはその年に巡遊する地域、黒マスはその年に巡遊しない地域を意味したそうです。

マスの色は年ごとに変化しました。色は前年の盤面のマスの色を元に塗り替えられます。

あるマスの上下左右に隣接するマスのうち、塗り替え前に黒だったマスの個数が偶数なら、塗り替え後のそのマスは白マス、奇数なら黒マスになります。

四隅のマスに隣接するマスは 2 つ、端のマス (四隅のマスを除く) に隣接するマスは 3 つ、端以外のマスに隣接するマスは 4 つあります。

例えば、白マスを . で、黒マスを # で表すとして、ある年の盤面が以下だった場合、

.#.
.##
.#.

翌年は以下のように塗り替えられます。

##.
###
##.

トモアキ君は、知られている最古の盤面が歴史書に載っているのを見付け、その盤面の塗り替え前の盤面を復元することを思い付きました。

最古の盤面が与えられるので、塗り替え前の盤面としてありうるものを 1 つ答えてください。ただし、そのような塗り替え前の盤面は必ず 1 つ以上存在するものとします。


入力

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

N
C1,1C1,2..C1,N
C2,1C2,2..C2,N
:
CN,1CN,2..CN,N
  • 1 行目には、列数と行数を表す整数 N (1 \leq N \leq 750) が与えられる。
  • 2 行目から N 行は、i 行目 j 列目のマスの色 Ci,j (1 \leq i, j \leq N) が与えられる。
  • 白マスを . として表現し、黒マスを # として表現するものとする。
  • 与えられる盤面には、少なくとも 1 つの塗り替え前の盤面がありうる。

部分点

  • 1 \leq{} N \leq{} 3 のケースに正解した場合、部分点として25点を与える。
  • 1 \leq{} N \leq{} 9 のケースに正解した場合、部分点としてさらに30点を与える。

出力

与えられた盤面の塗り替え前の色を 1 行に N 文字ずつ N 行で出力せよ。出力の末尾には改行をいれること。


入力例1

3
##.
###
##.

出力例1

.#.
.##
.#.

出力の盤面の 11 列目のマスについて、上にマスはありません。左にもマスはありません。右のマスは # です。 下のマスは . です。11 列目のマスの上下左右のマスで、# マスの個数が 1 となり、奇数なので塗り替え後の色は # です。

同様に、出力の盤面の 12 列目のマスについて、上にマスはありません。左のマスは . です。 下のマスは # です。 右のマスは . です。 # マスの個数が 1 となり、奇数なので塗り替え後の色は # です。

また同様に、出力の盤面の 13 列目のマスについて、上にマスはありません。左のマスは # です。下のマスは # です。右のマスはありません。# マスの個数が 2 となり、偶数なので塗り替え後の色は . です。

すべてのマスに対してこのような塗り替えを行うと、入力の盤面と一致するため正解です。


入力例2

5
.....
.....
.....
....#
...#.

出力例2

.....
.....
.....
.....
....#

入力例3

10
#...#.#.#.
.####.#..#
##..###..#
#...###...
.#.#.##...
..##.##..#
######..#.
.#.....#..
.#...#####
..##...###

出力例3

##########
....#.#.##
#..#.#.#.#
#.#..#..#.
..........
####..#.#.
#.#.#.#...
....####..
####..#.#.
##.#.#..#.

Source name

天下一プログラマーコンテスト2014 予選B

Submit提出する