题目
分析
这道题目的思路很直接：找一条路出去——这个可以用DFS或者BFS来解决。难点在于，在一个“无穷大”的迷宫里，怎么判断能否“走出去”？细想一下，程序不可能无限循环，但是有一个比较直接了当的判定方法：
如果走着走着（搜索算法），发现到了一个“同样”的点——这个点之前已经到过，但是不是上一次到过的点——就说明可以从“前一个基础迷宫”跑到这个肯定是“幻象”出来的迷宫里。以此类推，从这个“同样”的点显然可以到达下一个“同样”的点……这样就存在一条路，可以不断地“前进”，满足了题目的要求。
幻象的处理
只要想清楚幻象迷宫的构造方式，就知道，对于一个n*m的基础迷宫而言，每过n行m列，一个点的坐标其实就会重复。但是，坐标重复可以代表回来了，也可以代表穿过了一个基础迷宫而来。所以，A点到原来的A点，距离是0；而到了幻象出来的迷宫中的A'点，距离肯定不是0。这是分别点本身和幻象点的关键。
由此，对于一个点来说，要记录的东西就不光光是是否访问过了，还要记录经过了多少距离才访问到。
int vis[MAXN][MAXN][3];
//[0]: 是否访问过
//[][0]：x方向的偏移
//[][][0]：y方向的偏移只有这三个“坐标”完全一样，才是同样一个点。
DFS
想通这个，在DFS的时候的处理就比较直接：
- 如果找到了这样的
A和A'点，返回。
if (found)
{
return; // 如果已经找到循环路径，终止递归
}- 如果一个点之前已经访问过（
vis[x][y][0]!=0），但是位移和之前的位移不一样，它就是一个镜像点：找到了！返回！
if (vis[x][y][0] && (vis[x][y][1] != lx || vis[x][y][2] != ly))
{
found = 1;
return;
}- 否则就要常规处理，但还需要额外记录当前的偏移量
// 标记当前位置已访问，并记录当前位移
vis[x][y][1] = lx;
vis[x][y][2] = ly;
vis[x][y][0] = 1;
// 尝试四个方向移动
for (int i = 0; i < 4; ++i)
{
// 计算新的位置，考虑迷宫的周期性
int xx = (x + dx[i] + n) % n;
int yy = (y + dy[i] + m) % m;
// 计算新的位移
int lxx = lx + dx[i];
int lyy = ly + dy[i];
// 如果新位置不是墙壁，且满足未访问或位移不同，则继续DFS
if (!a[xx][yy])
{
if (vis[xx][yy][1] != lxx || vis[xx][yy][2] != lyy ||
!vis[xx][yy][0])
dfs(xx, yy, lxx, lyy);
}
}注意，这里有两对数值要更新：
- 下一个位置。取模的过程反应了幻象的特性。
int xx = (x + dx[i] + n) % n;
int yy = (y + dy[i] + m) % m;- 下个方向的位移：
int lxx = lx + dx[i];
int lyy = ly + dy[i];同时，为了尽量剪枝，在判定是否要进行下一个DFS的时候，需要判定：
- 不是墙壁：
!a[xx][yy] - 没访问过：
!vis[xx][yy][0] - 下个点的位移和现在算出来的位移不一样：
vis[xx][yy][1] != lxx || vis[xx][yy][2] != lyy
才进行下一个DFS。
答案
思考
-
数据结构设计
- 为什么用3维数组存储访问信息？
vis[x][y][0]：访问标记vis[x][y][1]：x方向位移vis[x][y][2]：y方向位移
- 这种设计如何帮助我们区分原点和幻象点
- 为什么用3维数组存储访问信息？
-
DFS剪枝策略
- 已找到解就立即返回
- 遇到已访问点但位移不同时停止
- 墙壁直接跳过
- 位移相同的点不重复访问
-
复杂度分析
- 时间复杂度：\(O(n * m * k)\)，
k是允许的最大位移 - 空间复杂度：\(O(n * m * 3)\)
- 时间复杂度：\(O(n * m * k)\)，