CF196B Infinite Maze

我们有一个 $n \times m$ 的矩形迷宫。每个格子要么是可通行的，要么是墙（不可通行）。一个小男孩发现了这个迷宫，并用它循环铺满了整个平面，使得平面变成了一个无限大的迷宫。现在在这个平面上，如果且仅如果格子 $((x \bmod n),(y \bmod m))$ 是墙，则格子 $(x, y)$ 也是墙。 在本题中，$(a \bmod b)$ 表示 $a$ 除以 $b$ 的余数。 小男孩站在平面上的某个格子上，他想知道自己是否能从起点无限远地走开。从格子 $(x, y)$ 他可以走向以下四个格子之一：$(x, y-1)$、$(x, y+1)$、$(x-1, y)$ 和 $(x+1, y)$，前提是要走去的格子不是墙。

第一行包含两个用空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 1500$），表示小男孩用于循环铺平面的迷宫的高度和宽度。 接下来 $n$ 行，每行包含 $m$ 个字符，描述了迷宫的布局。每个字符是如下之一：“\#” 表示墙，“.” 表示可通行的格子，“S” 表示小男孩的起点。 起点“S”一定是可通行的格子，且输入中恰好出现一次“S”。

如果小男孩能从起点无限远地走开，输出 “Yes”；否则，输出 “No”。

在第一个样例中，小男孩可以不断向上走下去，因为有一条“通路”可以垂直延伸。他只需要不断重复如下步骤：上、上、左、上、上、右、上。 而在第二个样例中，垂直方向的道路被阻断了。向左走的路也不行——下一份“复制”的迷宫会把小男孩困住。 由 ChatGPT 5 翻译