ストーリー

この問題は $2023$ 年 $3$ 月に作成された問題で、私が初めて作問したグリッド構築です。

出題に際して、難易度とフォーマットの調整を行いましたが、解法はほぼそのままです。

問題文

$H$ 行 $W$ 列の盤面があります。

盤面の各マスを白または黒で塗ります。このとき次の $3$ つの条件を満たすような塗り方は可能ですか？

• 全ての白いマスが連結 (任意の白いマス $x$ から白いマス $y$ まで、上下左右に隣接する白いマスのみを通って移動できる)
• 全ての黒いマスが連結 (任意の黒いマス $x$ から黒いマス $y$ まで、上下左右に隣接する黒いマスのみを通って移動できる)
• 白いマスと黒いマスが上下左右に隣接する箇所はちょうど $K$ 箇所

可能であればそのような盤面の例を出力してください。不可能であればそのことを報告してください。

制約

• 入力は全て整数
• $1 \leq H \leq 1000$
• $1 \leq W \leq 1000$
• $2 \leq HW$
• $0 \leq K \leq 2HW - H - W$

入力

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

$H\ W\ K$

出力

問題の条件を満たす盤面が存在する場合はその例を $1$ つ出力してください。存在しない場合は -1 を出力してください。

盤面の出力は、以下において盤面の $i$ 行 $j$ 列目のマスが黒いマスであれば $S_i$ の $j$ 文字目が #、白いマスであれば $S_i$ の $j$ 文字目が . となるようにしてください。サンプル $1$ も参考にしてください。

$S_1$
$S_2$
$\vdots$
$S_H$

最後に改行してください。

ビジュアライザ

出力結果のWeb版ビジュアライザがこちらで提供されています。

コンテスト中における、ビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。

また、ビジュアライザの仕様に関する質問は原則受け付けません。あくまで補助ツールとしてご利用ください。

サンプル

サンプル1

入力

3 3 5

出力

.#.
.#.
...

全ての白いマス、黒いマスがそれぞれ連結であり、黒いマスと白いマスが上下左右に隣接している箇所が $5$ 箇所あるため、問題の条件を満たしています。

2 2 1

-1

3 4 0

####
####
####