← 返回题目列表

AtCoder · abc276_e

H. 往返

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个网格 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.
  • If 1 \leq i \leq n - 1,然后 C_{x_i, y_i} = ..
  • If 1 \leq i \lt j \leq n - 1,然后 (x_i, y_i) \neq (x_j, y_j).
  • If 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} is 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