Score : $500$ points

问题描述

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

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:37:59