Infinite Maze

题意翻译

给定长宽分别为 $n,m$ 的迷宫 $a$。由 $a$ 可以形成一个无限大的迷宫。其中坐标为 $(i,j)$ 的位置，放置的东西为 $a_{(i-1)\bmod n+1,(j-1)\bmod n+1}$。 若某个位置为 `#` 则是墙，为 `.` 则是空气，为 `S` 则是起点。现在询问是否可以从起点出发到达无限远的地方。

题目描述

We've got a rectangular $ n×m $ -cell maze. Each cell is either passable, or is a wall (impassable). A little boy found the maze and cyclically tiled a plane with it so that the plane became an infinite maze. Now on this plane cell $ (x,y) $ is a wall if and only if cell  is a wall. In this problem  is a remainder of dividing number $ a $ by number $ b $ . The little boy stood at some cell on the plane and he wondered whether he can walk infinitely far away from his starting position. From cell $ (x,y) $ he can go to one of the following cells: $ (x,y-1) $ , $ (x,y+1) $ , $ (x-1,y) $ and $ (x+1,y) $ , provided that the cell he goes to is not a wall.

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ and $ m $ ( $ 1<=n,m<=1500 $ ) — the height and the width of the maze that the boy used to cyclically tile the plane. Each of the next $ n $ lines contains $ m $ characters — the description of the labyrinth. Each character is either a "\#", that marks a wall, a ".", that marks a passable cell, or an "S", that marks the little boy's starting point. The starting point is a passable cell. It is guaranteed that character "S" occurs exactly once in the input.

输出格式

Print "Yes" (without the quotes), if the little boy can walk infinitely far from the starting point. Otherwise, print "No" (without the quotes).

输入输出样例

输入样例 #1

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

输出样例 #1

Yes

输入样例 #2

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

输出样例 #2

No

说明

In the first sample the little boy can go up for infinitely long as there is a "clear path" that goes vertically. He just needs to repeat the following steps infinitely: up, up, left, up, up, right, up. In the second sample the vertical path is blocked. The path to the left doesn't work, too — the next "copy" of the maze traps the boy.