如何使用递归走出迷宫

本文关键字：迷宫 递归 何使用 | 更新日期: 2023-09-27 18:13:05

让我们考虑一个由整数矩阵表示的迷宫:0 -未访问，1 -障碍物(阻塞位置)，2 -访问，-1 -输出，(x,y) -开始位置。我想通过递归找到从开始到某个输出的路径。

int[] x_dir = new int[] { 0, 0, -1, 1 }; // x, x, x-1, x + 1
int[] y_dir = new int[] { -1, 1, 0, 0 }; // y-1, y+1, y, y
bool dfs(int[,] maze, int x, int y, int[] x_dir, int[] y_dir)
{
   if (maze[x, y] == -1) { return true; } // output cell marked -1 
   int i = 0;
   while (i < 4 && !dfs(maze, x + x_dir[i], y + y_dir[i], x_dir, y_dir))
   {
      ++i;
   }
   return (i > 4) ? false : true;
}

我有两个问题:我不知道如何处理边缘情况(IndexOutOfRangeException inside maze[x,y])和如何打印路径。

如何使用递归走出迷宫

要打印路径，您需要跟踪它，这建议为此添加一个参数。必须注意不要包括错误的转弯，或者至少在你知道它们是什么之后删除它们。

或者，如果您打印出每次调用dfs返回true时所采取的步骤，您将得到路径，但相反。

至于边缘(不是角落)的情况:你需要检查x+x_dir[i]和y+y_dir[i]是有效的索引进入迷宫之前，试图访问迷宫中的这些位置。

对于打印路径，您可以创建一个额外的矩阵并在其中存储信息。与用动态规划解决的最长子序列问题相同。

或您可以使用相同的矩阵，而不是创建一些额外的矩阵。要跟踪路径，只需在找到输出单元格时保存状态。

while (i < 4)
{ 
    if(!dfs(maze, x + x_dir[i], y + y_dir[i], x_dir, y_dir))
        ++i;
    else
        maze[x][y]=255;
}

，然后在元素255的单元格后面。

相关文章：