/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
縦 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}) は上下または左右に隣接する
制約
- 4 \leq H \times W \leq 10^6
- H, W は 2 以上の整数
- C_{i, j} は
S、.、#のいずれか - C_{i, j} =
Sとなる (i, j) がただ一つ存在する
入力
入力は以下の形式で標準入力から与えられる。
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
Score : 500 points
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