問題一覧 > 通常問題

No.3339 Tree on Checkerboard

レベル : / AI推定難易度 : 2800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 5
作問者 : 👑 kencho / テスター : cn_449 👑 みうね
お気に入りにしたユーザー ProblemId : 12735 / 自分の提出
問題文最終更新日: 2025-11-08 02:00:33
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 487 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。