B - Painting with Many Orders Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

N 行 N 列のグリッドがあります。 あなたはグリッドの各マスを、白色か黒色のどちらかで塗ります。

以下の条件を満たすような塗り方を 1 つ構成してください。

  • 白いマスは連結である。（どの 2 つの白いマスについても、辺で隣接した白いマスのみをたどることで行き来できる。）
  • すべての黒いマスは少なくとも 1 つの白いマスに辺で隣接している。
  • i 行目にある黒いマスの個数を p_i とすると、数列 P = (p_1, p_2, \ldots, p_N) は 0 から N-1 までの整数を並び替えた順列になっている。
  • j 列目にある黒いマスの個数を q_j とすると、数列 Q = (q_1, q_2, \ldots, q_N) は 0 から N-1 までの整数を並び替えた順列になっている。

制約

  • 2 \leq N \leq 500

入力

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

N

出力

問題文の条件を満たす塗り方のうち 1 つを以下の形式で出力せよ。 ここで、c_{i,j} はグリッドの i 行 j 列目のマスの色を表す文字である。

  • i 行 j 列目のマスが白色のとき、c_{i,j} は . とせよ。
  • i 行 j 列目のマスが黒色のとき、c_{i,j} は # とせよ。

余計な空白や改行を含めると Wrong Answer となることがあるので注意せよ。

c_{1,1}c_{1,2}\ldotsc_{1,N}
c_{2,1}c_{2,2}\ldotsc_{2,N}
\vdots
c_{N,1}c_{N,2}\ldotsc_{N,N}

入力例1

3

出力例1

..#
#.#
...

この出力は問題文のすべての条件を満たします。

条件を満たさない出力としては、次のようなものがあります。

.#.
##.
...

（白いマスが連結ではない。）

##.
#..
...

（白いマスに辺で隣接していない黒いマスがある。）

##.
...
..#

（Q = (1, 1, 1) であり、これは 0 から N-1 の順列ではない。）