76 lines
2.6 KiB
C++
76 lines
2.6 KiB
C++
#include<bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 1510;
|
||
struct coord {
|
||
int x;
|
||
int y;
|
||
};
|
||
//路径中的某个点，如果再次被访问到，并且，不是原来的前驱时，就可以交替进行这样的操作，不断外延出去。
|
||
//走迷宫下右上左
|
||
int dx[4] = {0, 1, 0, -1};
|
||
int dy[4] = {1, 0, -1, 0};
|
||
|
||
int n, m;
|
||
int sx, sy;//出发点坐标
|
||
|
||
char g[N][N]; //地图
|
||
int book[N][N][3]; // book[u][v][0~2]分别表示：是否访问过，x和y
|
||
|
||
/**
|
||
* 功能：正数+负数取模
|
||
*/
|
||
int MOD(int a, int b) {
|
||
return (a % b + b) % b;
|
||
}
|
||
|
||
//广度优先搜索
|
||
bool bfs() {
|
||
queue<coord> q; //声明队列
|
||
q.push({sx, sy}); //将出发点放入队列
|
||
|
||
//标识起点已使用，并且第一次到达时，真实坐标是x,y
|
||
book[sx][sy][0] = 1, book[sx][sy][1] = sx, book[sx][sy][2] = sy;
|
||
|
||
//开始套路
|
||
while (!q.empty()) {
|
||
int x = q.front().x;
|
||
int y = q.front().y;
|
||
q.pop();
|
||
for (int i = 0; i < 4; ++i) {
|
||
int tx = x + dx[i];
|
||
int ty = y + dy[i];
|
||
//因为可能出现负数，使用负数取模运算
|
||
int r = MOD(tx, n), c = MOD(ty, m);
|
||
//如果不是墙
|
||
if (g[r][c] != '#') {
|
||
//如果走过.而且与上次过来的位置不一样的话，就是肯定能走出去
|
||
if (!book[r][c][0]) {
|
||
//没有走过，入队列
|
||
q.push({tx, ty});
|
||
//标识已使用，并且第一次到达的坐标是a,b
|
||
book[r][c][0] = 1, book[r][c][1] = tx, book[r][c][2] = ty;
|
||
} else if ((book[r][c][1] != tx || book[r][c][2] != ty)) return true;
|
||
}
|
||
}
|
||
}
|
||
return false;
|
||
}
|
||
|
||
int main() {
|
||
while (cin >> n >> m) {
|
||
//每次清空,地图数组不用每次清空，因为每次都全新读入，自
|
||
memset(book, 0, sizeof book);
|
||
//双重循环读入地图
|
||
// 注意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; //标识起点
|
||
}
|
||
//广度优先
|
||
if (bfs())cout << "Yes" << endl; //可以走出幻象迷宫
|
||
else cout << "No" << endl; //不能走出幻象迷宫
|
||
}
|
||
} |