洛谷迷宫问题的答案错误问题

Question

答案错误，有一半是对的，能帮我看看吗？最好能在原有代码上做出修改，必采纳!

#include <iostream>
using namespace std;
int a[10000][105], v[10000][105]; //访问数组v[]，1为已经访问过，0为未访问; //地图数组a[]，1时为空地，2时为障碍物
//dx,dy为方向输组
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int n, m, t, sx, sy, fx, fy,cnt = 0;
void dfs(int x, int y)
{
    if (x == fx && y == fy) //到达终点
    {
        cnt++;       //次数加一
        v[x][y] = 0;  //终点设置为未访问，其他位置回溯时候，由于只能访问一次，就不设置为未访问了
        v[sx][sy] = 0;      //起点也设置为未访问
        return;
    }
    for (int i = 0; i < 4; ++i)     //没有到达终点，就往四个方向继续做试探(默认为：右下左上)
    {
        int tx, ty;    //四个方向试探的辅助变量
        tx = x + dx[i];
        ty = y + dy[i];
        if (a[tx][ty] == 1 && v[tx][ty] == 0) //空地且未访问
        {
            v[tx][ty] = 1;   //设置为已经访问
            dfs(tx,ty);      //这里的下面不设置返回时遇到的方格为0了，因为每个方格只能访问一次
        }
    }
}

int main()
{
    cin >> n >> m >> t;
    for (int i = 1; i <= n; ++i)    //初始化a数组全为1
    {
        for (int j = 1; j <= m; ++j)
        {
            a[i][j] = 1;    
        }
    }
    cin >> sx >> sy >> fx >> fy;       //输入起点和终点坐标

    if (sx == fx && sy == fy)   //终点和起点相同，直接输出0
    {
        cout << 0;
        return 0;
    }
    for (int k = 1; k <= t; ++k)     //设置障碍物
    {
        int t1, t2;
        cin >> t1 >> t2;
        a[t1][t2] = 2;      //障碍物设置为2
    }
    v[sx][sy] = 1; //将起点设置为已经访问
    dfs(sx, sy);   //递归搜索
    cout << cnt;
    return 0;
}

Answer 1

引自免费微信小程序：皆我百晓生

在你的代码中，你解决的是一个迷宫搜索问题，使用了深度优先搜索（DFS）算法。然而，对于可能存在的多个路径到达终点的情况，你的程序只计算了一条路径，并且没有确保回溯正确。当起点和终点之间存在多条路径时，cnt 只会记录一条路径的次数。

为了修正这个问题以获取所有从起点到终点的不同路径的数量，你需要对 DFS 算法进行改造，使其支持回溯。一种方法是使用栈来保存搜索路径，并在遇到障碍物或已访问节点时弹出栈顶元素并改变方向。但是，在本例中，由于题目限制每个格子只能访问一次，所以实际上我们并不需要处理多路径情况，只需确保DFS搜索能够完整探索所有可能性即可。

检查以下部分：

1. 在 dfs() 函数内，确保当你尝试的方向不可达时，能及时回到上一层搜索状态。
2. 当从一个节点移动到另一个节点时，应该立即标记当前节点为已访问，而不是仅在递归返回时才标记。

针对你当前的代码，我注意到一个小问题：在 dfs() 函数内部，如果已经到达终点，则应立即结束搜索过程，而不仅仅增加计数器 cnt。为此，请修改 dfs() 函数如下：

void dfs(int x, int y)
{
    if (x == fx && y == fy) // 到达终点
    {
        cnt++;       // 次数加一
        return;      // 直接返回，不再继续试探其他方向
    }
    for (int i = 0; i < 4; ++i)
    {
        int tx, ty;
        tx = x + dx[i];
        ty = y + dy[i];
        if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && a[tx][ty] == 1 && v[tx][ty] == 0) 
        {   // 添加边界条件判断，防止越界
            v[tx][ty] = 1;
            dfs(tx, ty);
            v[tx][ty] = 0; // 这里需恢复未访问状态，以便于回溯
        }
    }
}

另外，请确认输入数据格式是否与代码逻辑匹配，包括迷宫大小、起始点和终点坐标以及障碍物的位置等信息。在给出的代码片段中，似乎没有显式处理输入数据边界错误的问题，这也是潜在错误来源之一。