当前没有测试数据。

E - 圆周旅行

得分：500分

问题描述

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

每个方格可以是以下三种之一：初始点、道路和障碍物。
如果方格$(i, j)$是初始点，则它的字符表示为$C_{i, j} = $ S；如果方格$(i, j)$是道路，则它的字符表示为$C_{i, j} = $ .；如果方格$(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})$垂直或水平相邻。

约束

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

输入

从标准输入读入数据，输入格式如下：

$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