102764: [AtCoder]ABC276 E - Round Trip

Problem Statement

We have a grid with $H$ rows from top to bottom and $W$ columns from left to right. Let $(i, j)$ denote the $i$-th row from the top $(1 \leq i \leq H)$ and $j$-th column from the left $(1 \leq j \leq W)$.

Each square is one of the following: the initial point, a road, and an obstacle.
A square $(i, j)$ is represented by a character $C_{i, j}$. The square is the initial point if $C_{i, j} = $ S, a road if $C_{i, j} = $ ., and an obstacle if $C_{i, j} = $ #. There is exactly one initial point.

Determine whether there is a path of length $4$ or greater that starts at the initial point, repeats moving vertically or horizontally to an adjacent square, and returns to the initial point without going through an obstacle or visiting the same square multiple times except at the beginning and the end.
More formally, determine whether there are an integer $n$ and a sequence of squares $(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)$ that satisfy the following conditions.

• $n \geq 4$.
• $C_{x_0, y_0} = C_{x_n, y_n} = $ S.
• If $1 \leq i \leq n - 1$, then $C_{x_i, y_i} = $ ..
• If $1 \leq i \lt j \leq n - 1$, then $(x_i, y_i) \neq (x_j, y_j)$.
• If $0 \leq i \leq n - 1$, then square $(x_i, y_i)$ and square $(x_{i+1}, y_{i+1})$ are vertically or horizontally adjacent to each other.

Constraints

• $4 \leq H \times W \leq 10^6$
• $H$ and $W$ are integers greater than or equal to $2$.
• $C_{i, j}$ is S, ., or #.
• There is exactly one $(i, j)$ such that $C_{i, j} =$ S.

Input

The input is given from Standard Input in the following format:

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

Output

If there is a path that satisfies the conditions in the Problem Statement, print Yes; otherwise, print No.

Sample Input 1

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

Sample Output 1

Yes

The path $(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)$ satisfies the conditions.

Sample Input 2

2 2
S.
.#

Sample Output 2

No

Sample Input 3

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

Sample Output 3

No

问题描述

我们有一个从上到下有$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})$相互垂直或水平相邻。

约束条件

• $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。

样例输入1

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

样例输出1

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 2
S.
.#

样例输出2

No

样例输入3

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

样例输出3

No