No.1434 Make Maze
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 56
作問者 : tyawanmusi / テスター : chineristAC
タグ : / 解いたユーザー数 56
作問者 : tyawanmusi / テスター : chineristAC
問題文最終更新日: 2021-03-19 18:43:05
問題文
$H$ 行 $W$ 列のマス目があります( $H,W$ は奇数)。上から $i$ 行目、左から $j$ 列目のマスを マス $(i,j)$ とします。
茶碗蒸しくんはマス $(1,1)$ にいます。これから茶碗蒸しくんは上下左右に隣接している障害物のないマスに移動することを繰り返してマス $(H,W)$ に移動します。
茶碗蒸しくんが移動を始める前に、あなたは障害物を好きなだけマスに置くことができます。ただし、障害物の配置は以下の条件に従わなければなりません。
- $i,j$ が共に奇数であるマス $(i,j)$ には障害物が置かれていない。
- $i,j$ が共に偶数であるマス $(i,j)$ には障害物が置かれている。
- 障害物が置かれていない任意の異なる $2$ マスにおいて、茶碗蒸しくんがその $2$ マス間を移動する、同じマスを $2$ 回以上通らないような経路がただ一通りのみ存在する。
例えば、次の図のような障害物の配置は条件を満たしています。
対して、次の図のような障害物の配置は条件を満たしていません。
茶碗蒸しくんがマス $(H,W)$ に移動するための最小移動回数が $X$ となるように障害物を配置してください。
制約
- 入力はすべて整数
- $3 \le H,W \le 10^3$
- $H,W$ は奇数
- $1 \le X \le HW$
入力
以下の形式に従って標準入力で与えられる。
$H\ W\ X$
出力
条件を満たす配置が不可能なとき、-1
を出力してください。
可能なとき、長さ $W$ の .
,#
からなる文字列を $H$ 行出力してください。
マス $(i,j)$ に障害物を置くとき、$i$ 行目の $j$ 文字目を #
、そうではないとき .
にしてください。
最後に改行してください。
サンプル
サンプル1
入力
5 7 18
出力
...#... ##.#.## ...#... .###.#. .....#.
この障害物の配置において、茶碗蒸しくんは移動を $18$ 回することでマス $(H,W)$ に到達できます。
また、条件に違反していないため、この出力は正しいです。
サンプル2
入力
11 11 121
出力
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。