测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A6279. 幻想迷宫

编程题 普及+/提高
知识点

题目描述

幻象迷宫可以认为是**无限大**的,不过它是由若干个 $N \times M$ 的矩阵**平铺重复**组成的。

给出一个 $N \times M$ 的字符矩阵,表示从坐标 $(0,0)$ 到 $(N-1,M-1)$ 这一块区域内的情况:

- . 表示道路;
- # 表示墙;
- S 表示 Welcome24ever 和 fangz 的起始位置(恰好出现一次)。

整个无限迷宫是通过这个 $N \times M$ 的矩阵无限复制平铺得到的。
也就是说,对于无限迷宫中任意一个格子 $(x,y)$($x,y$ 可以是任意整数),如果把它“折回”到基础矩阵中:

- 令
- $i \equiv x \pmod N$,$0 \le i < N$;
- $j \equiv y \pmod M$,$0 \le j < M$;
- 那么:
- 若基础矩阵上 $(i,j)$ 位置是 .S,则 $(x,y)$ 是**道路**;
- 若基础矩阵上 $(i,j)$ 位置是 #,则 $(x,y)$ 是**墙**。

Welcome24ever 和 fangz 可以从起点出发,在道路上移动,每一步可以**上下左右**移动一格,但不能移动到墙上。

如果它们可以走到**距离起点任意远**的地方(也就是在这个无限的平铺迷宫中,能到达无穷远处),就认为它们能够**走出幻象迷宫**。

现在请你告诉它们:是否能够走出幻象迷宫?
- 如果能走到距离起点无限远处,输出 Yes
- 否则输出 No

输入格式

- 第一行包含两个整数 $N, M$,表示基础矩阵的行数和列数;
- 接下来 $N$ 行,每行一个长度为 $M$ 的字符串,只包含 .#S,表示从 $(0,0)$ 到 $(N-1,M-1)$ 的这一块区域。

保证每组数据中恰好有一个 S

输出格式

对于每组数据,输出一行:

- 若 Welcome24ever 和 fangz 能够走到距离起点无限远处,输出:

```text
Yes
```

- 否则输出:

```text
No
```

输入输出样例

输入 #1
5 4
##.#
##S#
#..#
#.##
#..#
输出 #1
Yes
输入 #2
5 4
##.#
##S#
#..#
..#.
#.##
输出 #2
No

说明/提示

- $1 \le N, M \le 1500$;
上一题 去做题 下一题