分数: 525 点
问题陈述
Snuke 计划在 AtCoder Land 建造一个迷宫作为新景点。迷宫被表示为一个网格 N 行和 M 列,右上角单元格的上边缘是入口,右下单元格的下边缘是出口。他将通过在相邻单元格之间适当放置墙壁来创建迷宫。
他喜欢简单的迷宫,所以他希望从入口到出口的路径能够准确通过 K 细胞没有任何分支。确定是否有可能创建这样一个迷宫,如果可能的话,建造一个。
例如下图中, N=3 和 M=3,并且墙壁放置在实线处(除了入口和出口之外,墙壁始终放置在外周周围)。在这种情况下,从入口到出口的路径恰好经过 7 细胞没有任何分支。

以下是正式声明。
有一个网格 N 行和 M 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。对于每对侧面相邻的单元,您可以决定是否在它们之间放置一堵墙。确定是否可以放置墙来满足以下条件,如果可能,则构建一个这样的放置。
考虑一个无向图 G 与 NM 顶点。的每个顶点 G 由一对整数唯一标记 (i,j)\ (1\leq i\leq N, 1\leq j\leq M)。 两个不同的顶点 (i_1,j_1) 和 (i_2,j_2) 由边连接当且仅当 |i_1-i_2|+|j_1-j_2|=1 并且相应的单元格之间没有墙 网格上的 (i_1,j_1) 和 (i_2,j_2) 。
条件:存在一条简单路径 K 连接两个顶点的顶点 (1,M) 和 (N,M),以及包含顶点的连接组件 (1,M) 和 (N,M) 仅包含此路径。
约束
- 2\leq N \leq 100
- 1\leq M \leq 100
- 1\leq K\leq NM
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M K
输出
如果没有满足条件的墙的放置,则打印 No。否则,请按以下格式打印一份此类布置。如果存在多个有效展示位置,则可以打印其中任何一个。
另请参阅下面的示例输出,以更好地理解复杂的输出格式。
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 分别代表入口、出口、墙壁和牢房,并且
单元格之间的 ? 表示可以放置墙的位置。更换 ? 两个水平相邻的单元格之间 | 如果放置了一堵墙,并且 . 否则。更换 ? 两个垂直相邻的单元格之间 - 如果放置了一堵墙,并且 . 否则。
以下是正式说明。
- 输出应包括 2N+2 行。线 1 应包含字符串
Yes和行 2 to 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} is|如果单元格之间放置了一堵墙 (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} is-如果单元格之间放置了一堵墙 (i,j) 和 (i+1,j),和.否则。 - 线 2N+2 应该是一个串联
+重复 2M-1 次,G,和+,按此顺序。
- 线 2 应该是一个串联
示例输入 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+