Round Trip

题目描述

我们有一个从上到下有 $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

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

标签: AtCoder|abc276E

来源

AtCoder|abc276E