深度优先搜索求两个点之间的最短距离

Question

洛谷P1747 好奇怪的游戏求两个点之间的最小值，使用bfs深搜，为什么不对，只拿了80分

```c++
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=29;
int dis[N][N];
bool str[N][N];
int x1,x2,y1,y2;
struct point{
    int x;
    int y;
};
int dx[12]={-2,-2,-2,-2,-1,1,2,2,2,2,1,-1};
int dy[12]={-2,-1,1,2,2,2,2,1,-1,-2,-2,-2};
int bfs(int x,int y,int ex,int ey){
    str[x][y]=true;
    dis[x][y]=0;
    point cur,next;
    queue<point>que;
    cur.x=x;
    cur.y=y;
    que.push(cur);
    while(!que.empty()){
        cur=que.front();
        que.pop();
        if(cur.x==ex&&cur.y==ey) 
          return dis[cur.x][cur.y];
        for(int i=0;i<12;i++){
            int nx=cur.x+dx[i];
            int ny=cur.y+dy[i];
            if(nx<=0||ny<=0 ) continue;
            if(str[nx][ny]==false){
                str[nx][ny]=true;
                dis[nx][ny]=dis[cur.x][cur.y]+1;
                next.x=nx;
                next.y=ny;
                que.push(next);
            }
        }
    }
}
int main(){
    cin>>x1>>y1>>x2>>y2;
    int s1=bfs(x1,y1,1,1);
    memset(str,false,sizeof(str));
    memset(dis,0,sizeof(dis));
    int s2=bfs(x2,y2,1,1);
    cout<<s1<<endl<<s2<<endl;
    return 0;
}

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

问题在于你的代码使用了深度优先搜索（DFS）而非广度优先搜索（BFS），而题目要求的是寻找两点间的最短路径，这应该使用BFS算法。在DFS中，我们通常不会保证找到最短路径，因为它的搜索顺序可能不是按距离递增的。以下是修改后的代码，使用BFS算法来解决这个问题：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=29;
int dis[N][N];
bool str[N][N];
int x1, x2, y1, y2;

// 其他代码保持不变

int bfs(int x, int y, int ex, int ey) {
    str[x][y] = true;
    dis[x][y] = 0;
    point cur, next;
    queue<point> que;
    cur.x = x;
    cur.y = y;
    que.push(cur);

    while (!que.empty()) {
        cur = que.front();
        que.pop();

        if (cur.x == ex && cur.y == ey) {
            return dis[cur.x][cur.y];
        }

        // 修改这里，使用邻接节点而不是12个方向
        for (int i = 0; i < 4; i++) { // 只考虑上下左右四个方向
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx <= 0 || ny <= 0) continue;
            if (str[nx][ny] == false) {
                str[nx][ny] = true;
                dis[nx][ny] = dis[cur.x][cur.y] + 1;
                next.x = nx;
                next.y = ny;
                que.push(next);
            }
        }
    }
}

int main() {
    cin >> x1 >> y1 >> x2 >> y2;
    int s1 = bfs(x1, y1, 1, 1);
    memset(str, false, sizeof(str));
    memset(dis, 0, sizeof(dis));
    int s2 = bfs(x2, y2, 1, 1);
    cout << s1 << endl << s2 << endl;
    return 0;
}

在这个修改后的版本中，我只考虑了四个基本的方向（上、下、左、右），因为题目描述中的好奇怪的游戏似乎限制了移动方向。同时，我将bfs函数里的for (int i = 0; i < 12; i++)更改为for (int i = 0; i < 4; i++)，以匹配新的移动策略。现在这个程序应该能够正确计算两点之间的最短距离了。