基于栈实现的老鼠走迷宫DFS算法原理及实现方法咨询

核心算法代码 #

mark[1,0]=1; top=1; stack[top].row=1; stack[top].col=0;   
stack[top].dir=1; while (top>0) {
    loc = pop();
    cr=loc.row; cc=loc.col; cd=loc.dir;
    while (cd <= 4) {
         nr=cr+move[cd].r;  nc=cc+move[cd].c;
         if (nr==grow && nc==gcol) {
              for(i=0; i<=top; i++) printLoc(stack[i]);
              print(cr, cc); print(grow, gcol);
              return;
         }
         if (maze[nr][nc]==0 && mark[nr][nc]==0) {
              mark[nr][nc] = 1;
              loc.row=cr; loc.col=cc; loc.dir=cd+1;
              push(loc);
              cr=nr; cc=nc; cd=1;
         }
         else cd=cd+1;
    } 
} 
print("no path in maze");

基础变量说明 #

• maze：二维迷宫矩阵，值为1代表障碍不可通行，值为0代表可通行路径
• mark：二维标记数组，值为1代表对应坐标已经走过，避免重复遍历绕圈
• move：方向偏移映射数组，对应规则如下：
  • 方向1：move[1] = (0,1)，列+1，向右移动
  • 方向2：move[2] = (1,0)，行+1，向下移动
  • 方向3：move[3] = (0,-1)，列-1，向左移动
  • 方向4：move[4] = (-1,0)，行-1，向上移动
• stack：栈结构，存储已走路径的节点，每个节点包含3个属性：row（所在行）、col（所在列）、dir（下一次回溯时要尝试的方向）
• top：栈顶指针，值大于0代表栈内还有未处理的路径节点
• grow、gcol：迷宫终点对应的行、列坐标

算法运行逻辑逐段讲解 #

1. 初始化阶段 #

mark[1,0]=1; top=1; 
stack[top].row=1; stack[top].col=0; 
stack[top].dir=1;

这部分是起点初始化，本算法默认起点坐标为(1,0)，首先标记该点已经走过，将起点压入栈中，初始要尝试的方向设为向右（对应dir=1）。

2. 外层循环（栈非空则继续探索） #

外层循环while (top>0)的逻辑是：只要栈里还有未处理完的路径节点，就继续搜索路径。

• 每次先弹出栈顶节点loc = pop()，拿到当前所在位置cr（当前行）、cc（当前列），以及该节点接下来要尝试的方向cd。

3. 内层循环（逐个尝试4个移动方向） #

内层循环while (cd <=4)的逻辑是：从当前要尝试的方向开始，依次测试4个方向是否可通行：

1. 计算下一个尝试的坐标：nr=cr+move[cd].r; nc=cc+move[cd].c，即当前坐标加上方向偏移量得到目标坐标(nr, nc)
2. 优先判断是否到达终点：如果(nr, nc)和终点坐标(grow, gcol)一致，说明已经找到可行路径，直接输出栈中存储的所有历史路径节点，再输出当前坐标和终点坐标，直接结束程序。
3. 如果未到达终点，判断目标坐标是否可通行：满足maze[nr][nc]==0（不是障碍）且mark[nr][nc]==0（之前没走过）两个条件即可通行：
   • 先标记该坐标已走过mark[nr][nc] = 1
   • 将当前节点（坐标cr, cc）的下一次尝试方向设为cd+1，重新压回栈中：本次已经尝试过cd方向可行，下次回溯回来就不需要再试该方向，直接试下一个方向即可
   • 将当前坐标更新为可通行的目标坐标(nr, nc)，方向重置为1，在新的坐标点重新从向右开始尝试4个方向
4. 如果当前方向不可通行（是障碍/已经走过/超出边界），就将方向值+1cd=cd+1，测试下一个方向。

如果4个方向全部测试完都不可通行，说明当前节点是死路，不需要再压回栈中，直接回到外层循环弹出上一个路径节点继续测试，也就是DFS的回溯逻辑。
如果外层循环结束（栈已经为空）还没有找到终点，说明整个迷宫没有可行路径，输出对应提示即可。

落地实现注意事项 #

• 代码示例省略了边界判断，实际实现时需要先校验nr和nc是否在迷宫的合法行、列范围内，避免数组越界报错
• 栈可以直接使用编程语言自带的实现，比如Python的list自带的append/pop方法、C++的std::stack类、Java的Stack类都可以直接使用
• mark数组大小和迷宫矩阵保持一致即可，初始全部赋值为0
• 方向数组可以预先定义，注意下标从1开始匹配题目给出的方向规则，比如Python可以定义为move = [(), (0,1), (1,0), (0,-1), (-1,0)]

内容的提问来源于stack exchange，提问作者Andrew Choi