/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
すぬけくんは、AtCoder Land の新たな目玉アトラクションとして迷路を建設しようと考えています。 迷路は縦 N 行・横 M 列のグリッドとして表され、右上のマスの上端が入口、右下のマスの下端が出口です。 すぬけくんは、隣接するマスの間に適切に壁を配置することで迷路を作ります。
すぬけくんは簡単な迷路が大好きなので、入口から出口までの道順は枝分かれを一切持たずにちょうど K マスを通るようなものにしたいです。 そのような迷路を作ることが可能か判定し、可能ならば 1 つ構築してください。
例えば以下の図では、N=3,M=3 であり、実線で書かれているところに壁が配置されています（入口と出口を除く外周部には必ず壁が配置されるものとします）。 このとき、入口から出口までの道順は枝分かれを一切持たずにちょうど 7 マスを通っています。
厳密には以下の通りです。
縦 N 行・横 M 列のグリッドがあります。 上から i 行目、左から j 列目のマスを (i,j) と表記します。 あなたは、辺で隣接する任意の 2 マスの間それぞれについて壁を置くか置かないか決めることができます。 壁を置く場所をうまく定めることで以下の条件を満たすことができるか判定し、できるならば実際に 1 つ構築してください。
NM 頂点からなる無向グラフ G を考える。G の各頂点は 2 つの整数の組 (i,j)\ (1\leq i\leq N, 1\leq j\leq M) によって互いに相異なるラベルが付けられている。 相異なる 2 頂点 (i_1,j_1),(i_2,j_2) は、|i_1-i_2|+|j_1-j_2|=1 かつグリッド上の 2 マス (i_1,j_1),(i_2,j_2) の間に壁が置かれていない場合、またその場合に限り辺で結ばれている。
条件：K 頂点からなり 2 頂点 (1,M),(N,M) を結ぶような単純パスが存在し、また 2 頂点 (1,M),(N,M) を含む連結成分はこのパスのみからなる。
制約
- 2\leq N \leq 100
- 1\leq M \leq 100
- 1\leq K\leq NM
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
条件を満たす壁の配置が存在しないならば No を出力し、存在するならばそのうちの 1 つを以下の形式で出力せよ。
条件を満たす壁の配置が複数存在する場合は、そのどれを出力してもよい。
複雑な出力形式のため、下記の出力例も参考にしてください。
Yes +++++ \dots +++S+ +o?o? \dots ?o?o+ +?+?+ \dots +?+?+ +o?o? \dots ?o?o+ +?+?+ \dots +?+?+ \vdots +o?o? \dots ?o?o+ +?+?+ \dots +?+?+ +o?o? \dots ?o?o+ +++++ \dots +++G+
ここで、S, G, +, o はそれぞれ入口、出口、壁、マスを表し、マスとマスの間にある ? は壁を置くことができる場所である。
横に隣接する 2 マスの間にある ? は、壁を置くならば | で、壁を置かないならば . で置き換えよ。
縦に隣接する 2 マスの間にある ? は、壁を置くならば - で、壁を置かないならば . で置き換えよ。
厳密には以下の通りである。
- 出力は 2N+2 行からなり、1 行目には文字列
Yesを、2 行目から 2N+2 行目には以下で説明されるように長さ 2M+1 の文字列を出力する。- 2 行目には、2M-1 個の
+,S,+をこの順に連結して出力する。 - 1+2i 行目 (1\leq i\leq N) には、
+,o, c_{i,1},o, c_{i,2}, \dots, c_{i,M-1},o,+をこの順に連結して出力する。 ここで、c_{i,j} はマス (i,j),(i,j+1) の間に壁を置くならば|、置かないならば.である。 - 2+2i 行目 (1\leq i\leq N-1) には、
+, r_{i,1},+, r_{i,2},+, \dots,+, r_{i,M},+をこの順に連結して出力する。 ここで、r_{i,j} はマス (i,j),(i+1,j) の間に壁を置くならば-、置かないならば.である。 - 2N+2 行目には、2M-1 個の
+,G,+をこの順に連結して出力する。
- 2 行目には、2M-1 個の
入力例 1
3 3 7
出力例 1
Yes +++++S+ +o.o.o+ +.+-+-+ +o.o.o+ +-+-+.+ +o.o|o+ +++++G+
問題文中の図と同じ壁の配置です。
入力例 2
3 3 2
出力例 2
No
入力例 3
4 1 4
出力例 3
Yes +S+ +o+ +.+ +o+ +.+ +o+ +.+ +o+ +G+
Score : 525 points
Problem Statement
Snuke is planning to build a maze as a new attraction in AtCoder Land. The maze is represented as a grid with N rows and M columns, with the top edge of the top-right cell being the entrance and the bottom edge of the bottom-right cell being the exit. He will create the maze by appropriately placing walls between adjacent cells.
He loves simple mazes, so he wants the path from the entrance to the exit to pass through exactly K cells without any branches. Determine if it is possible to create such a maze, and if possible, construct one.
For example, in the following figure, N=3 and M=3, and walls are placed at the solid lines (walls are always placed around the outer perimeter except for the entrance and exit). In this case, the path from the entrance to the exit passes through exactly 7 cells without any branches.
Below is a formal statement.
There is a grid with N rows and M columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left. For each pair of side-adjacent cells, you can decide whether to place a wall between them. Determine whether it is possible to place walls to satisfy the following condition, and if it is possible, construct one such placement.
Consider an undirected graph G with NM vertices. Each vertex of G is uniquely labeled by a pair of integers (i,j)\ (1\leq i\leq N, 1\leq j\leq M). Two distinct vertices (i_1,j_1) and (i_2,j_2) are connected by an edge if and only if |i_1-i_2|+|j_1-j_2|=1 and there is no wall between the corresponding cells (i_1,j_1) and (i_2,j_2) on the grid.
Condition: there exists a simple path with K vertices that connects the two vertices (1,M) and (N,M), and the connected component containing the vertices (1,M) and (N,M) consists only of this path.
Constraints
- 2\leq N \leq 100
- 1\leq M \leq 100
- 1\leq K\leq NM
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K
Output
If there is no placement of walls that satisfies the condition, print No. Otherwise, print one such placement in the following format. If multiple valid placements exist, any of them can be printed.
See also the sample outputs below to better understand the complicated output format.
Yes +++++ \dots +++S+ +o?o? \dots ?o?o+ +?+?+ \dots +?+?+ +o?o? \dots ?o?o+ +?+?+ \dots +?+?+ \vdots +o?o? \dots ?o?o+ +?+?+ \dots +?+?+ +o?o? \dots ?o?o+ +++++ \dots +++G+
Here, S, G, +, and o represent the entrance, exit, a wall, and a cell, respectively, and ? between cells represents a position where a wall can be placed. Replace ? between two horizontally adjacent cells with | if a wall is placed, and . otherwise. Replace ? between two vertically adjacent cells with - if a wall is placed, and . otherwise.
Below is a formal instruction.
- The output should consist of 2N+2 lines. Line 1 should contain the string
Yes, and lines 2 to 2N+2 should contain strings of length 2M+1 as described below.- Line 2 should be a concatenation of
+repeated 2M-1 times,S, and+, in this order. - Line 1+2i (1\leq i\leq N) should be a concatenation of
+,o, c_{i,1},o, c_{i,2}, \dots, c_{i,M-1},o,+, in this order. Here, c_{i,j} is|if a wall is placed between cells (i,j) and (i,j+1), and.otherwise. - Line 2+2i (1\leq i\leq N-1) should be a concatenation of
+, r_{i,1},+, r_{i,2},+, \dots,+, r_{i,M},+, in this order. Here, r_{i,j} is-if a wall is placed between cells (i,j) and (i+1,j), and.otherwise. - Line 2N+2 should be a concatenation of
+repeated 2M-1 times,G, and+, in this order.
- Line 2 should be a concatenation of
Sample Input 1
3 3 7
Sample Output 1
Yes +++++S+ +o.o.o+ +.+-+-+ +o.o.o+ +-+-+.+ +o.o|o+ +++++G+
This is the same placement of walls as in the figure in the problem statement.
Sample Input 2
3 3 2
Sample Output 2
No
Sample Input 3
4 1 4
Sample Output 3
Yes +S+ +o+ +.+ +o+ +.+ +o+ +.+ +o+ +G+