c++ - 在迷宫 C++ 中查找路径是否存在

Question

我的代码出现运行时错误。我不知道如何解决它？它甚至不适用于较小的矩阵 4 X 4 。该问题的矩阵大小不超过 20 x 20。

代码:

#include <iostream>
using namespace std;
int a[20][20];
bool findpath(int ar[][20],int i,int j,int size)
{
    if (ar[i][j]==0 || i>(size-1) || j>(size-1) || i<0 || j<0)
        return false;
    if (ar[i][j]==2)
        return true;
    if ((findpath(ar,i+1,j,size)) || (findpath(ar,i,j+1,size)) 
    || (findpath(ar,i-1,j,size)) || (findpath(ar,i,j-1,size)))
        return true;
    return false;
}
int main() {
    int t;
    cin>>t;
    while(t--)
    {   int n;
        cin>>n;

        int r,c;

        //size = n;
        for(int i =0 ;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>a[i][j];
                if (a[i][j]==1)
                   { r=i;
                    c=j;
                   }
            }

        }
        //cout<<r<<c;
        bool b = findpath(a,r,c,n);
        if (b)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;

    }
    return 0;
}

输入:

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

输出:

YES

但是我得到了 Segmentation Fault (SIGSEGV)

Answer 1

检查声明的评估顺序 if (ar[i][j]==0 || i>(size-1) || j>(size-1) || i<0 || j<0) .您将访问 ar[i][j] 来评估第一个表达式，即使 i 也是如此。超出范围或j出界了。它应该按顺序排列，以便在 if 中发生短路时条件是你是安全的/不会导致未定义的行为，例如:

if (i < 0 || i >= size || j < 0 || j >= size || ar[i][j]==0) .现在如果i < 0它短路并且不需要检查其余部分并且不评估ar[i][j] .

正如您所提到的，这是行不通的，这是一个工作版本，我将对其进行解释。首先，我将您的 C 样式数组更改为 vector ，而是使用它们来获取行和列的大小。我还从用户那里删除了您的输入，您可以稍后添加这些输入并帮助简化问题。

#include <vector>
bool findpath(vector<vector<int>>ar,int i,int j,vector<vector<int>>& visited)
{

    if (i < 0 || i >= ar.size() || j < 0 || j >= ar[0].size() || ar[i][j] == 0 || visited[i][j]) return false;

    if (ar[i][j]==2) return true;

    visited[i][j] = true;
    if(findpath(ar,i+1,j,visited) || findpath(ar,i,j+1,visited) || findpath(ar,i-1,j,visited) || findpath(ar,i,j-1,visited)) return true;
    visited[i][j] = false;

    return false;
}
int main() {
        const int rows = 3;
        const int cols = 3;
        vector<vector<int>> arr = {{ 0 , 3 , 2 },
                                   { 3 , 3 , 0 },
                                   { 1 , 3 , 0 }};

        vector<vector<int>> visited(rows,vector<int>(cols,false));
        bool b = findpath(arr,1,1,visited);
        if (b)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;


    return 0;
}

在主函数中我刚刚使用了一个 vector<vector<int>>描述您发布的链接中的迷宫。 i和 j下例中的起点是 1和 1 .还有一个visited与迷宫相同的二维数组。这会阻止你通过标记你已经覆盖的点来进行无限递归，如果它们没有解决你设置 vector[i][j] = false回溯。最后，如果您的任何安排返回有效结果，我们将返回，否则我们将返回 false。

您可以查看此演示 live here

您还提到 1是起点。在示例中，我已经从 1 开始了.您可以在 main 中添加一个循环，以首先计算出起点的坐标。同样，这应该足以让您继续前进。