← 返回题目列表

Codeforces · 196/B

B. 无限迷宫

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

我们有一个矩形的 n × m 单元迷宫。每个单元要么是可通行的,要么是一堵墙(不可通行)。一个小男孩发现了这个迷宫,并用它循环地平铺一个平面,使这个平面变成了一个无限的迷宫。现在,在这个平面上,单元格 (x, y) 是一面墙,当且仅当单元格 $$( x \mod n, y \mod m )$$ 是一面墙。

在这个问题中 $$a \bmod b$$ 是数字 a 除以数字 b 的余数。

小男孩站在飞机上的某个牢房里,他想知道他是否可以从起始位置走得无限远。从单元格 (x, y) 他可以前往以下单元格之一:(x, y - 1)、(x, y + 1)、(x - 1, y) 和 (x + 1, y),前提是他前往的单元格不是墙壁。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 1500) — 男孩用来循环平铺平面的迷宫的高度和宽度。

接下来的n行每行包含m个字符——迷宫的描述。每个字符要么是“#”,标记一堵墙,要么是“.”,标记可通过的单元格,要么是“S”,标记小男孩的起点。

起点是一个可通过的单元格。保证字符“S”在输入中恰好出现一次。

输出

如果小男孩可以从起点走无限远,则打印“Yes”(不带引号)。否则,打印“No”(不带引号)。

示例

输入 #1

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

输出 #1

Yes

输入 #2

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

输出 #2

No

注意

在第一个示例中,小男孩可以无限上升,因为有一条垂直的“清晰路径”。他只需要无限重复以下步骤:上、上、左、上、上、右、上。

在第二个示例中,垂直路径被阻挡。左边的路也行不通——迷宫的下一个“副本”困住了男孩。