题目描述
点击查看题目
题目背景
（喵星人 LHX 和 WD 同心协力击退了汪星人的入侵，不幸的是，汪星人撤退之前给它们制造了一片幻象迷宫。）
WD：呜呜，肿么办啊……
LHX：momo...我们一定能走出去的！
WD：嗯，+U+U！
题目描述
幻象迷宫可以认为是无限大的，不过它由若干个 \(N\times M\) 的矩阵重复组成。矩阵中有的地方是道路，用 \(\verb!.!\) 表示；有的地方是墙，用 \(\verb!#!\) 表示。LHX 和 WD 所在的位置用 \(\verb!S!\) 表示。也就是对于迷宫中的一个点\((x,y)\)，如果 \((x \bmod n,y \bmod m)\) 是 \(\verb!.!\) 或者 \(\verb!S!\)，那么这个地方是道路；如果 \((x \bmod n,y \bmod m)\) 是\(\verb!#!\)，那么这个地方是墙。LHX 和 WD 可以向上下左右四个方向移动，当然不能移动到墙上。
请你告诉 LHX 和 WD，它们能否走出幻象迷宫（如果它们能走到距离起点无限远处，就认为能走出去）。如果不能的话，LHX 就只好启动城堡的毁灭程序了……当然不到万不得已，他不想这么做。
输入格式
输入包含多组数据，以 EOF 结尾。
每组数据的第一行是两个整数 \(N,M\)。
接下来是一个 \(N\times M\) 的字符矩阵，表示迷宫里 \((0,0)\) 到 \((n-1,m-1)\) 这个矩阵单元。
输出格式
对于每组数据，输出一个字符串，Yes 或者 No。
样例 #1
样例输入 #1
5 4
##.#
##S#
#..#
#.##
#..#
5 4
##.#
##S#
#..#
..#.
#.##
样例输出 #1
Yes
No
提示
- 对于 \(30\%\) 的数据，\(1\le N,M\le 20\)；
- 对于 \(50\%\) 的数据，\(1\le N,M\le 100\)；
- 对于 \(100\%\) 的数据，\(1\le N,M\le 1500\)，每个测试点不超过 \(10\) 组数据。
思路
从起点往外走，坐标取模，如果一个点被走两次，那么证明可以循环往复，判断方法为当前取模以后的坐标和真实的循环坐标是否相等。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1510;
char s[N][N];
int n, m;
bool vis[N][N];
int cx[N][N], cy[N][N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
bool dfs(int x, int y, int lx, int ly) {
vis[x][y] = 1;
cx[x][y] = lx;
cy[x][y] = ly;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
int nlx = lx + dx[i];
int nly = ly + dy[i];
nx = (nx % n + n) % n;
ny = (ny % m + m) % m;
if (s[nx][ny] == '#') continue;
if (!vis[nx][ny]) {
if (dfs(nx, ny, nlx, nly)) return true;
}
else {
if ((cx[nx][ny] != nlx) || (cy[nx][ny] != nly)) return true;
}
}
return false;
}
void solve() {
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; i++) cin >> s[i];
int sx = -1, sy = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] == 'S') {
sx = i, sy = j;
s[i][j] = '.';
break;
}
}
}
if (dfs(sx, sy, sx, sy)) cout << "Yes\n";
else cout << "No\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> n >> m) solve();
return 0;
}