题目描述

縦 $H$ 行、横 $W$ 列のマス目があり、上から $i\ \,\ (1\ \leq\ i\ \leq\ H)$ 行目、左から $j\ \,\ (1\ \leq\ j\ \leq\ W)$ 列目のマスを $(i,\ j)$ と表します。

各マスは「始点」「道」「障害物」のいずれかです。
マス $(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 を出力せよ。

题目大意

判断是否可以从起点出发，找到一条长度大于等于四且不重复经过某点（起点除外）最后回到起点的路径。

--mfeitveer

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

Yes

2 2
S.
.#

No

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

No

提示

制約

• $4\ \leq\ H\ \times\ W\ \leq\ 10^6$
• $H,\ W$ は $2$ 以上の整数
• $C_{i,\ j}$ は S、.、# のいずれか
• $C_{i,\ j}\ =$ S となる $(i,\ j)$ がただ一つ存在する

Sample Explanation 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) $ という経路が条件を満たします。