83 lines
2.1 KiB
C++
83 lines
2.1 KiB
C++
#include<bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 1510;
|
||
int n, m;
|
||
//坐标结构体
|
||
struct coord {
|
||
int 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;
|
||
}
|
||
|
||
int book[N][N];
|
||
char g[N][N];
|
||
|
||
|
||
//随便写的hash函数
|
||
int Hash(int x, int y) {
|
||
return x * 10000 + y;//因为x,y的极值是1500,就是4位，如果x*10000,最小是1万以上，再加上y,y就在后4位
|
||
//也可以少乘点
|
||
}
|
||
|
||
/**
|
||
* 功能：广度优先搜索
|
||
* @param x 坐标x
|
||
* @param y 坐标y
|
||
* @return 是否能走出迷宫
|
||
*/
|
||
bool bfs(int x, int y) {
|
||
queue<coord> q;
|
||
//入队列
|
||
q.push((coord) {x, y});
|
||
|
||
book[x][y] = Hash(x, y);
|
||
while (!q.empty()) {
|
||
coord u = q.front(), v;
|
||
q.pop();
|
||
|
||
for (int i = 0; i < 4; i++) {
|
||
v.x = u.x + dx[i];
|
||
v.y = u.y + dy[i];
|
||
int r = MOD(v.x, n);//下一步的相对位置x
|
||
int c = MOD(v.y, m);//下一步的相对位置y
|
||
int h = Hash(v.x, v.y);
|
||
//如果下一个位置不是障碍物
|
||
if (g[r][c] != '#') {
|
||
//如果下一个位置没有走过
|
||
if (!book[r][c]) {
|
||
book[r][c] = h;//记录本次hash值
|
||
q.push(v);//入队列
|
||
} else if (book[r][c] != h) return true;//上次的hash值与本次的不一样，说明来自不同的前驱，就表示可以走出去
|
||
}
|
||
}
|
||
}
|
||
return false;
|
||
}
|
||
|
||
int main() {
|
||
while (cin >> n >> m) {
|
||
//清空状态数组
|
||
memset(book, 0, sizeof(book));
|
||
//读入
|
||
int x, y;
|
||
for (int i = 0; i < n; ++i)
|
||
for (int j = 0; j < m; ++j) {
|
||
cin >> g[i][j];
|
||
if (g[i][j] == 'S')x = i, y = j; //标识起点
|
||
}
|
||
//广度优先搜索
|
||
if (bfs(x, y)) printf("Yes\n");
|
||
else printf("No\n");
|
||
}
|
||
return 0;
|
||
} |