AT_abc358_f.[ABC358F] Easiest Maze

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

すぬけ君打算在 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$ 且这两个格子之间没有墙壁，则它们之间有一条边。

条件：存在一条包含 $K$ 个顶点、连接 $(1,M)$ 和 $(N,M)$ 的简单路径，并且包含 $(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$ $2 N + 2$ 行，第 $1$ $1$ 行输出字符串 Yes，第 $2$ $2$ 行到第 $2N+2$ $2 N + 2$ 行按如下方式输出，每行长度为 $2M+1$ $2 M + 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，+，依次连接。

输入输出样例

输入#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+

说明/提示

数据范围

$2\leq N \leq 100$
$1\leq M \leq 100$
$1\leq K\leq NM$
输入均为整数

样例解释 1

与题目描述中的图示墙壁配置相同。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页