Time Limit: 2 sec / Memory Limit: 256 MB
問題文
天下一王国の歴史を学んでいるトモアキ君は、王国を導いた偉大な英雄である 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
.#. .## .#.
出力の盤面の 1 行 1 列目のマスについて、上にマスはありません。左にもマスはありません。右のマスは # です。 下のマスは . です。1 行 1 列目のマスの上下左右のマスで、# マスの個数が 1 となり、奇数なので塗り替え後の色は # です。
同様に、出力の盤面の 1 行 2 列目のマスについて、上にマスはありません。左のマスは . です。 下のマスは # です。 右のマスは . です。 # マスの個数が 1 となり、奇数なので塗り替え後の色は # です。
また同様に、出力の盤面の 1 行 3 列目のマスについて、上にマスはありません。左のマスは # です。下のマスは # です。右のマスはありません。# マスの個数が 2 となり、偶数なので塗り替え後の色は . です。
すべてのマスに対してこのような塗り替えを行うと、入力の盤面と一致するため正解です。
入力例2
5 ..... ..... ..... ....# ...#.
出力例2
..... ..... ..... ..... ....#
入力例3
10 #...#.#.#. .####.#..# ##..###..# #...###... .#.#.##... ..##.##..# ######..#. .#.....#.. .#...##### ..##...###
出力例3
########## ....#.#.## #..#.#.#.# #.#..#..#. .......... ####..#.#. #.#.#.#... ....####.. ####..#.#. ##.#.#..#.