No.3339 Tree on Checkerboard
Problem Statement
There is an $N \times N$ grid painted in a black and white checkerboard pattern. Let $(i,\ j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left. Cell $(i,\ j)$ is painted black if $(i + j)\bmod 2= 0$, and white if $(i + j)\bmod 2= 1$.
Is it possible to repaint $0$ or more black cells white so that the set of all white cells forms a tree?
If it is possible, show one example; if it is impossible, report so.
Here, the set of all white cells forms a tree if the graph obtained by taking each white cell as a vertex and adding an edge between every pair of white cells adjacent vertically or horizontally on the grid is $1$ tree.
Constraints
- All inputs are integers.
- $2 \leq N \leq 2000$
Input
The input is given from Standard Input in the following format.
$N$
Output
For each case, print -1 if no repainting of cells satisfying the condition exists; otherwise, print one example in the following format.
$S_1$ $S_2$ $\vdots$ $S_N$
$S_i$ is a string of length $N$, and the $j$-th character of $S_i$ must be . if cell $(i,\ j)$ is white after repainting, and # if it is black.
Print a newline at the end.
Sample
Sample 1
Input
5
Output
#...# .#.#. ..... .#.#. ..#..
The upper part of the figure below shows the repainting of the grid corresponding to the sample output.
The repainting on the lower left is another valid solution, while the repainting on the lower right does not satisfy the condition because it contains a cycle at the position marked with red lines.
Sample 2
Input
2
Output
#. ..
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
cn_449