dfs中的死循环问题

Question

请问下面代码的逻辑出了什么问题？为何是死循环？

#include<iostream>
using namespace std;
int MinPath = 70;
int far = -1;
int dp[8][2] = { {1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2} };
int map[10][10] = { 0 };

void dfs(int a, int b)
{
    //越界和重复访问的节点，退回
    if (a <= 0 || a > 8 || b <= 0 || b > 8 || map[a][b]==1 )return;
    //有效距离++
    far++;
    //未访问过的节点标记
    map[a][b] = 1;
    //每次到终点都更新距离far
    if (map[a][b] == 2 && far < MinPath) MinPath = far;
    //dfs8个方向
    for (int i = 0; i < 8; i++)    
    {
        int x = a + dp[i][0];
        int y = b + dp[i][1];
        dfs(x,y);
    }
    //遍历完了回退时恢复现场
    map[a][b] = 0;
    return;
}

int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    map[c][d] = 2;
    dfs(a, b);
    if (MinPath == 70)cout << "-1" << endl;
    else cout << MinPath << endl;
    return 0;
}

Answer 1

该回答引用自GPT-3.5,由博主GISer Liu编写：

问题出现在你的dfs函数中。具体来说，出现了无限递归调用的情况，导致死循环。
在你的dfs函数中，你对每个方向都进行了递归调用：
cppCopy code

for (int i = 0; i < 8; i++) {
int x = a + dp[i][0];
int y = b + dp[i][1];
dfs(x, y);
}

然而，在这里，你没有考虑到一个重要的情况，就是当从一个点（a，b）出发，到达下一个点（x，y）时，如果（x，y）已经被访问过了（map[x][y] ==
1），那么你应该停止继续往下递归调用，否则就会形成无限递归调用的情况，导致死循环。
解决方法是在递归调用之前，增加判断条件，如果下一个点已经被访问过，则不再继续递归调用。修改后的代码如下：
cppCopy code

for (int i = 0; i < 8; i++) {
int x = a + dp[i][0];
int y = b + dp[i][1];
// 如果下一个点已经被访问过，则不再继续递归调用
if (map[x][y] != 1) {
dfs(x, y);
}
}

这样修改后，就可以避免死循环的问题了。

如果该回答解决了您的问题，请采纳！如果没有，请参考以下方案进行修订