在二维数组中解决迷宫问题

Question

我已经查看了许多关于如何有效解决迷宫问题的文章和问题，但是在这里我想确认我的代码存在哪些问题。请考虑以下迷宫：

2 1 0 0 3
0 1 0 1 1
0 1 0 0 1
0 1 1 0 0
0 0 0 0 0

这里有一些数字，其中1代表墙壁，0代表路径。（源点是2，终点是3）。我需要输出是否存在一条路径。

int y=0;
        while(y==0)
        {
            robo1(n,m,maze);//this function adds 2 to any '0'/'3' in (i,j+1),(i+1,j),(i-1,j),(i,j-1) (if exists),where (i,j) is 2
            robo2(n,m,k2,maze);//this function adds 3 to any '0'/'2' in (i,j+1),(i+1,j),(i-1,j),(i,j-1) (if exists), where (i,j) is 3
            if(find5(n,m,maze)==1)//this function returns 1 if there is '5' in the maze
                y++;
            if(find0(n,m,maze)==0)//this function returns 0 if there are no '0' in the maze
                break;
        }
        if(find0(n,m,maze)==0 && y==0)
            printf("-1\n");//no path
        else
            printf("1\n");//there is a path

我的想法是，如果在任意数量的循环后，在迷宫中找到了一个五，那么这意味着有一条路径。 但是，在代码实现该函数时，我得到错误的答案，并且有时会发生运行时错误。 上述逻辑是否存在任何缺陷？

- yobro97

---

请提供 robo1、robo2、find5 和 find0 的实现代码。运行时错误意味着在这些函数中可能越界了，但没有代码很难确定。 - buld0zzr

对我来说，这个方法并不清晰。你了解深度优先搜索吗？ - Codor

问题很可能出在 robo* 和 find* 上，所以请按照 @buld0zzr 的说法发布。我认为这里的逻辑是正确的（虽然不是“最佳”），因为它基本上是一种暴力双向BFS。 - shole

Answer 1

总体想法基本可行，但是细节决定成败。

然而，有一种情况即使正确实施你的方法也无法奏效：

  2 1 0 0 0
  1 1 0 1 1 
  0 0 0 1 3

即使房间里有0，2和3都被墙壁“关闭”，你的循环也永远不会结束。因为尽管周围有0，但两个机器人函数都不会改变任何东西。

一个简单的解决方案是，在机器人实际上至少改变了矩阵中的一个值时从它们那里返回0/1，并在这种情况下退出。

请注意，这不是解决迷宫问题的有效方法（您的代码将一遍又一遍地检查相同的单元格）。

- 6502

---

展示算法本身有问题的好例子（我想是实现方面的问题）！ - shole

谢谢......我已经研究了一些方法，比如DFS和A*，它们比上述方法更有效......只是想知道这种方法的缺陷。 - yobro97