← 返回题目列表

AtCoder · abc358_f

I. 最简单的迷宫

中文机器翻译题面 查看原题

分数: 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,和 +,按此顺序。

示例输入 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+