AT_abc276_e [ABC276E] Round Trip

题目描述

有一个高 $H$ 行、宽 $W$ 列的网格，从上到下第 $i$ 行、从左到右第 $j$ 列的格子记作 $(i, j)$。

每个格子可能是“起点”、“道路”或“障碍物”之一。
格子 $(i, j)$ 的状态用字符 $C_{i, j}$ 表示，若 $C_{i, j} = \texttt{S}$，则为起点；若 $C_{i, j} = \texttt{.}$，则为道路；若 $C_{i, j} = \texttt{\#}$，则为障碍物。起点格子仅有一个。

请判断是否存在一条从起点出发，只能上下左右移动、且不经过障碍物，最终回到起点的长度不少于 $4$ 的路径，并且除起点外路径上不重复经过同一个格子。
更严格地说，判断是否存在满足以下条件的整数 $n$ 和格子序列 $(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)$：

• $n \geq 4$
• $C_{x_0, y_0} = C_{x_n, y_n} = \texttt{S}$
• 对于 $1 \leq i \leq n-1$，有 $C_{x_i, y_i} = \texttt{.}$
• 对于 $1 \leq i < j \leq n-1$，有 $(x_i, y_i) \neq (x_j, y_j)$
• 对于 $0 \leq i \leq n-1$，格子 $(x_i, y_i)$ 与 $(x_{i+1}, y_{i+1})$ 必须在上下或左右相邻

输入格式

输入按以下格式从标准输入读入。

$H$ $W$
$C_{1, 1} \ldots C_{1, W}$
$\vdots$
$C_{H, 1} \ldots C_{H, W}$

输出格式

如果存在满足题意的路径，输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

4 4
....
#.#.
.S..
.##.

输出 #1

Yes

输入输出样例 #2

输入 #2

2 2
S.
.#

输出 #2

No

输入输出样例 #3

输入 #3

5 7
.#...#.
..#.#..
...S...
..#.#..
.#...#.

输出 #3

No

说明/提示

限制

• $4 \leq H \times W \leq 10^6$
• $H, W$ 均为不小于 $2$ 的整数
• $C_{i, j}$ 只会是 S、.、# 之一
• 仅有一个格子 $C_{i, j} = \texttt{S}$

样例解释 1

存在如下路径满足条件：
$(3, 2) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 4) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 3) \rightarrow (3, 2)$。

由 ChatGPT 4.1 翻译