103585: [Atcoder]ABC358 F - Easiest Maze

Problem Statement

Snuke is planning to build a maze as a new attraction in AtCoder Land. The maze is represented as a grid with $N$ rows and $M$ columns, with the top edge of the top-right cell being the entrance and the bottom edge of the bottom-right cell being the exit. He will create the maze by appropriately placing walls between adjacent cells.

He loves simple mazes, so he wants the path from the entrance to the exit to pass through exactly $K$ cells without any branches. Determine if it is possible to create such a maze, and if possible, construct one.

For example, in the following figure, $N=3$ and $M=3$, and walls are placed at the solid lines (walls are always placed around the outer perimeter except for the entrance and exit). In this case, the path from the entrance to the exit passes through exactly $7$ cells without any branches.

Below is a formal statement.

There is a grid with $N$ rows and $M$ columns. Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left. For each pair of side-adjacent cells, you can decide whether to place a wall between them. Determine whether it is possible to place walls to satisfy the following condition, and if it is possible, construct one such placement.

Consider an undirected graph $G$ with $NM$ vertices. Each vertex of $G$ is uniquely labeled by a pair of integers $(i,j)\ (1\leq i\leq N, 1\leq j\leq M)$. Two distinct vertices $(i_1,j_1)$ and $(i_2,j_2)$ are connected by an edge if and only if $|i_1-i_2|+|j_1-j_2|=1$ and there is a wall between the corresponding cells $(i_1,j_1)$ and $(i_2,j_2)$ on the grid.

Condition: there exists a simple path with $K$ vertices that connects the two vertices $(1,M)$ and $(N,M)$, and the connected component containing the vertices $(1,M)$ and $(N,M)$ consists only of this path.

Constraints

• $2\leq N \leq 100$
• $1\leq M \leq 100$
• $1\leq K\leq NM$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$ $K$

Output

If there is no placement of walls that satisfies the condition, print No. Otherwise, print one such placement in the following format. If multiple valid placements exist, any of them can be printed.

See also the sample outputs below to better understand the complicated output format.

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+

Here, S, G, +, and o represent the entrance, exit, a wall, and a cell, respectively, and ? between cells represents a position where a wall can be placed. Replace ? between two horizontally adjacent cells with | if a wall is placed, and . otherwise. Replace ? between two vertically adjacent cells with - if a wall is placed, and . otherwise.

Below is a formal instruction.

• The output should consist of $2N+2$ lines. Line $1$ should contain the string Yes, and lines $2$ to $2N+2$ should contain strings of length $2M+1$ as described below.
  • Line $2$ should be a concatenation of + repeated $2M-1$ times, S, and +, in this order.
  • Line $1+2i$ $(1\leq i\leq N)$ should be a concatenation of +, o, $c_{i,1}$, o, $c_{i,2}$, $\dots$, $c_{i,M-1}$, o, +, in this order. Here, $c_{i,j}$ is | if a wall is placed between cells $(i,j)$ and $(i,j+1)$, and . otherwise.
  • Line $2+2i$ $(1\leq i\leq N-1)$ should be a concatenation of +, $r_{i,1}$, o, $r_{i,2}$, o, $\dots$, o, $r_{i,M}$, +, in this order. Here, $r_{i,j}$ is - if a wall is placed between cells $(i,j)$ and $(i+1,j)$, and . otherwise.
  • Line $2N+2$ should be a concatenation of +, G, and + repeated $2M-1$ times, in this order.

Sample Input 1

3 3 7

Sample Output 1

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

This is the same placement of walls as in the figure in the problem statement.

Sample Input 2

3 3 2

Sample Output 2

No

Sample Input 3

4 1 4

Sample Output 3

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

问题描述

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)$之间有墙壁。

条件：存在一个包含$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到$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}$，o，$r_{i,2}$，o，$\dots$，o，$r_{i,M}$，+，按此顺序。其中，$r_{i,j}$是-如果在单元格$(i,j)$和$(i+1,j)$之间放置了墙壁，否则是.。
  • 第$2N+2$行应为+，G，然后是+重复$2M-1$次，按此顺序。

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