Easiest Maze

题目描述

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-i_2|+|j_1-j_2|=1$ 且对应网格上的格子 $(i_1,j_1)$ 与 $(i_2,j_2)$ 之间没有墙时，两个不同的顶点 $(i_1,j_1)$ 和 $(i_2,j_2)$ 之间有一条边。 条件：存在一条包含 $K$ 个顶点的简单路径，该路径连接两个顶点 $(1,M)$ 与 $(N,M)$，并且包含顶点 $(1,M)$ 与 $(N,M)$ 的连通分量仅由这条路径构成。

输入格式

输入从标准输入给出，格式如下： $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 行到第 $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$、以及 $+$ 按此顺序拼接而成的字符串。

3 3 7

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

3 3 2

No

4 1 4

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

提示

$2\leq N \leq 100$ $1\leq M \leq 100$ $1\leq K\leq NM$ 所有输入值均为整数。这与问题陈述中图示的墙的放置方式相同。

标签: AtCoder|abc358F

来源

AtCoder|abc358F