一、题意分析
题意：给你一个\(n \times m\)的迷宫\(g\)(\(x\)，\(y\)范围是\(0 \sim n - 1\)和\(0 \sim m - 1\)），\(\#\)不能走，\(.\)可以走，\(S\)作为起点，现在将迷宫扩展成无穷大，扩展方法是：任意一个\((x, y)\)位置的字符\(c = g(x \% n, y \% m)\)，现在问你可不可以从起点处走到无穷远处。
举个栗子：
原始迷宫\(5 \times 5\)为中间的黄色区域，标红色的位置的坐标为\((-2, -4)\), 而 \((-2) % 5 = 3\), \((-4) % 5 = 1\), 所以\((-2, -4)\)位置处，应该和\(g(3, 1)\)相同，所以为\(S\)。
二、解题思路
对于一个位置\(A(x, y)\)如果能够走到另一个位置\(B(p, q)\), \(A≠B\)，并满足\(A\)和\(B\)在对应的\(n\times m\)图中的相对位置相同（意思是：\(p \% n = x \% n\), \(q \% m = y \% m\)），那么不断重复这个过程，就一定能走到无穷远处。所以考虑从起点（位于原图中，扩展的图中的其他\(S\)看成是\(.\)）开始\(dfs，bfs\)（此处是flood fill），一旦两次都遍历到了原图上的同一位置，并且这两次遍历到的点不同，那么说明可以走到无穷远处，否则不能。
注意红色部分：假设两次遍历到的点为\(（x，y）\)和\(（p，q）\), 那么遍历到原图上的同一位置指的是\(p \% n = x \% n\), \(q \% m = y \% m\)（是就相对位置而言的）
一开始我是每遍历到一个点\((x, y)\)就对原图上的\((x \% n, y \% m)\)标记访问过，然后在后面的遍历过程中一旦发现一个位置\(（p, q）\)有\(（p \% n, q \% m）\)已经被访问过，那么就认为能够走到无穷远，这是错的，因为有可能\((x, y)\)和\((p, q)\)是同一个点。
由于模运算的不可逆，意思就是说，如果只是简单的在访问到\(（x，y）\)时，对\(（x \% n，y \% m）\)标记已访问，那么在下一次搜索到某点\(（p, q）\)时就算\(（p \% n，q \% m）\)恰好为\((x, y)\)标记过的地方，也不能肯定\((p, q)\)和\((x, y)\)不是同一点，所以有必要对于原图中的每一个位置\((u, v)\)保存一下第一次访问到它（指\(x \% n = u, y \% m = v\)）的坐标(\(x\), \(y\))。
三、bfs常规解法
#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; //不能走出幻象迷宫
}
}
四、bfs取hash降维解法
#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;
}
五、dfs常规解法
#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;
}