77 lines
2.6 KiB
C++
77 lines
2.6 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 1510;//题目要求是1500
|
||
//https://www.cnblogs.com/tomori/p/14320956.html
|
||
int n, m;
|
||
|
||
char g[N][N]; //邻接矩阵,也就是二维数据保存地图
|
||
int st[N][N][3]; // st[u][v][0~2]分别表示：是否访问过，x和y
|
||
|
||
//走迷宫下右上左
|
||
int dx[4] = {0, 1, 0, -1};
|
||
int dy[4] = {1, 0, -1, 0};
|
||
|
||
/**
|
||
* 功能：正数+负数取模
|
||
*/
|
||
int MOD(int a, int b) {
|
||
return (a % b + b) % b;
|
||
}
|
||
|
||
bool success;
|
||
/**
|
||
* 功能：在邻接矩阵上面的深度优先搜索,从x,y这个点出发，是不是能走出幻象迷宫
|
||
* @param x
|
||
* @param y
|
||
* @return
|
||
*/
|
||
void dfs(int x, int y) {
|
||
for (int i = 0; i < 4; i++) { //遍历四个方向
|
||
int tx = x + dx[i], ty = y + dy[i]; //得到下一步的坐标
|
||
//因为可能出现负数，使用负数取模运算
|
||
int r = MOD(tx, n), c = MOD(ty, m);
|
||
//有的地方是墙，用'#'表示
|
||
if (g[r][c] != '#') {
|
||
if (st[r][c][0]) { //如果此位置走过
|
||
if (st[r][c][1] != tx || st[r][c][2] != ty) {
|
||
success = true; //并且不是从当前的位置过来的，就是有其它一条道路走过来的,表示可以走通
|
||
return;
|
||
}
|
||
} else {
|
||
//第一次访问到它（指x % n = u, y % m = v）的坐标(x, y)。
|
||
st[r][c][0] = 1, st[r][c][1] = tx, st[r][c][2] = ty;
|
||
//开始递归下一个位置
|
||
dfs(tx, ty);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//循环接收多次,ctrl+d结束
|
||
while (cin >> n >> m) {
|
||
//清空状态数组
|
||
memset(st, 0, sizeof st);
|
||
success = false;
|
||
int sx, sy;//出发点
|
||
//双重循环读入地图
|
||
// 注意i是从0开始，到n-1结束,这是因为：表示迷宫里(0,0)到(n-1,m-1)这个矩阵单元。
|
||
// 注意j是从0开始，到m-1结束,这是因为：表示迷宫里(0,0)到(n-1,m-1)这个矩阵单元。
|
||
for (int i = 0; i < n; i++)
|
||
for (int j = 0; j < m; j++) {
|
||
cin >> g[i][j];
|
||
//记录出发点
|
||
if (g[i][j] == 'S') sx = i, sy = j;
|
||
}
|
||
|
||
//第一次访问到它（指x % n = u, y % m = v）的坐标(x, y)。
|
||
st[sx][sy][0] = 1, st[sx][sy][1] = sx, st[sx][sy][2] = sy;
|
||
//深度优先搜索
|
||
dfs(sx, sy);
|
||
|
||
if (success)cout << "Yes" << endl; //可以走出幻象迷宫
|
||
else cout << "No" << endl; //不能走出幻象迷宫
|
||
}
|
||
return 0;
|
||
} |