[ABC358] F - Easiest Maze

2024-06-15

F - Easiest Maze

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 525 分

题面

Snuke 打算在 AtCoder Land 建造一个迷宫作为新的景点。迷宫表示为一个行列的网格，其中右上角的顶点是入口，右下角的底部是出口。他将通过在相邻单元格之间适当放置墙壁来创建迷宫。

他喜欢简单的迷宫，所以他希望从入口到出口的路径通过正好个单元格而且没有分支。确定是否可能创建这样一个迷宫，如果可能，构建一个。

例如，在下图中，且，实线处放置墙壁（墙壁始终放置在外部周边除了入口和出口）。在这种情况下，从入口到出口的路径通过了正好个单元格且没有分支。

下面是一个正式的陈述。

有一个行列的网格。记为从上到下第行、从左到右第列的单元格。对于每对相邻侧面的单元格，您可以决定它们之间是否放置一堵墙。

确定是否可能放置墙壁以满足以下条件，并且如果可能，构建一个这样的放置墙壁。

考虑一个无向图，具有个顶点。的每个顶点都由一对整数唯一标识。当且仅当网格上对应单元格和之间有一堵墙时，才连接的两个不同顶点和。

条件：存在一条包含个顶点的简单路径连接顶点和，且包含顶点和的连通分量仅包含该路径。

限制条件

所有输入值均为整数。

输入

输入以以下格式从标准输入给出：

输出

如果没有满足条件的墙壁放置方式，则打印 No。否则，以以下格式打印其中一个有效的放置方式。

查看下面的示例输出了解复杂的输出格式。

Yes
+++++ +++S+
+o?o? ?o?o+
+?+?+ +?+?+
+o?o? ?o?o+
+?+?+ +?+?+

+o?o? ?o?o+
+?+?+ +?+?+
+o?o? ?o?o+
+++++ +++G+

这里，S，G，+ 和 o 分别表示入口、出口、墙壁和单元格，两个水平相邻单元格之间的 ? 表示可以放置墙壁的位置。如果放置了墙壁，将 ? 替换为 |；如果未放置墙壁，则替换为 .。两个垂直相邻单元格之间的 ? ，如果放置了墙壁，则用 - 替换；否则用 . 替换。

下面是一个正式指导。

输出应包括行。第行应包含字符串 Yes，第行到第行应包含长度为的字符串，具体描述如下。
- 第行应由 + 重复次、S 和 + 依此排列组成。
- 第行 () 应由 +、o、、o、、、、o、+ 依此排列组成。这里，如果在单元格和之间放置了墙壁，则为 |；否则为 .。
- 第行 () 应由 +、、o、、o、、o、、+ 依此排列组成。这里，如果在单元格和之间放置了墙壁，则为 -；否则为 .。
- 第行应由 +、G 和 + 重复次、依此排列组成。

输入样例 1

3 3 7

输出样例 1

Yes
+++++S+
+o.o.o+
+.+-+-+
+o.o.o+
+-+-+.+
+o.o|o+
+++++G+

这是题面中图中所示的墙壁放置方式。

输入样例 2

3 3 2

输出样例 2

输入样例 3

4 1 4

输出样例 3

Yes
+S+
+o+
+.+
+o+
+.+
+o+
+.+
+o+
+G+