最简单的迷宫

题目描述

Snuke 计划在 AtCoder Land 建造一个新设施——迷宫。迷宫用 $N$ 行 $M$ 列的网格表示，最右上角格子的上边缘是入口，最右下角格子的下边缘是出口。他将在相邻格子之间适当放置墙壁来建造迷宫。

他喜欢简单的迷宫，因此希望从入口到出口的路径恰好经过 $K$ 个格子，且没有任何分叉。判断能否建造这样的迷宫，如果可能，请构造一个。

例如，在下图中，$N=3$，$M=3$，墙壁放置在实线处（除入口和出口外，外围总是有墙壁）。此时，从入口到出口的路径恰好经过 $7$ 个格子，且没有分叉。

下面是形式化描述。

有一个 $N$ 行 $M$ 列的网格。设 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。对于每对边相邻的格子，你可以决定是否在它们之间放置墙壁。判断能否通过放置墙壁满足以下条件，如果可能，请构造一种放置方案。

考虑一个有 $NM$ 个顶点的无向图 $G$。$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)$ 之间没有墙壁。

条件：存在一条连接顶点 $(1,M)$ 和 $(N,M)$ 的、包含 $K$ 个顶点的简单路径，并且包含顶点 $(1,M)$ 和 $(N,M)$ 的连通分量只由这条路径组成。

输入格式

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

$N$ $M$ $K$

输出格式

如果不存在满足条件的墙壁放置方案，输出 No。否则，按以下格式输出一种放置方案。如果存在多种合法方案，可以输出任意一种。

输出格式比较复杂，请结合下面的样例输出来理解。

Yes
+++++ … +++S+
+o?o? … ?o?o+
+?+?+ … +?+?+
+o?o? … ?o?o+
+?+?+ … +?+?+
⋮
+o?o? … ?o?o+
+?+?+ … +?+?+
+o?o? … ?o?o+
+++++ … +++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、+ 的顺序拼接得到的字符串。这里，如果格子 $(i,j)$ 和 $(i,j+1)$ 之间放置了墙壁，则 $c_{i,j}$ 为 |，否则为 .。

第 $2+2i$ 行（$1\leq i\leq N-1$）是按 +、$r_{i,1}$、+、$r_{i,2}$、+、$\dots$、+、$r_{i,M}$、+ 的顺序拼接得到的字符串。这里，如果格子 $(i,j)$ 和 $(i+1,j)$ 之间放置了墙壁，则 $r_{i,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$
• 所有输入值均为整数。

提示

答案不唯一，输出任意合法解即可。