回路

题目描述

我们有一个从上到下 $H$ 行、从左到右 $W$ 列的网格。设 $(i, j)$ 表示从上数第 $i$ 行 $(1 \leq i \leq H)$、从左数第 $j$ 列 $(1 \leq j \leq W)$ 的方格。

每个方格是以下三种之一:起点、道路、障碍物。

方格 $(i, j)$ 用字符 $C_{i, j}$ 表示。若 $C_{i, j} =$ S 则为起点,若 $C_{i, j} =$ . 则为道路,若 $C_{i, j} =$ # 则为障碍物。恰好有一个起点。

判断是否存在一条长度至少为 $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} =$ S

若 $1 \leq i \leq n - 1$,则 $C_{x_i, y_i} =$ .

若 $1 \leq i \lt 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 4
....
#.#.
.S..
.##.

Yes

路径 $(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)$ 满足条件。

2 2
S.
.#

No

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

No

数据范围

• $4 \leq H \times W \leq 10^6$
• $H$ 和 $W$ 是大于等于 $2$ 的整数。
• $C_{i, j}$ 是 S、. 或 #。
• 恰好存在一个 $(i, j)$ 使得 $C_{i, j} =$ S。