c++ - 解决二维数组中的迷宫

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

我的想法是，如果在迷宫中找到任意数量的循环后出现 5，则表示存在路径。 但是在代码中实现这个功能时，我得到了错误的答案，有时还会出现运行时错误。 以上逻辑有没有漏洞？

Answer 1

总体思路应该差不多可行，但当然一切都在细节中。

然而，即使正确实现，您的方法也不会奏效的一种情况是:

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

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

一个简单的解决方案是，如果机器人实际上至少更改了矩阵中的一个值，则从机器人返回 0/1，并在这种情况没有发生时退出。

请注意，这不是解决迷宫的非常有效的方法(您的代码将多次检查相同的单元格)。