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`。

## 限制 - $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 翻译