好奇怪的游戏（BFS）

 

#include<bits/stdc++.h>
using namespace std;

int dx[] = {1,1,2,2,-1,-1,-2,-2,2,2,-2,-2};
int dy[] = {2,-2,1,-1,2,-2,1,-1,2,-2,2,-2};

int bfs(int a,int b){
    queue<pair<int,int>> q;
    vector<vector<int>> dis(20,vector<int>(20,-1)); // 20x20的棋盘，初始化所有位置的步数为-1
    dis[a][b] = 0;
    q.push({a,b});


    while(q.size()){
        auto [x,y] = q.front();
        q.pop();

        if(dis[0][0] != -1){//一旦目标位置 (0, 0) 的步数已经被计算出来,直提前结束 BFS。
            return dis[0][0];;
        }

        for(int i=0;i<12;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx>=0 && nx<20 && ny>=0 && ny<20 && dis[nx][ny]==-1){
                dis[nx][ny] = dis[x][y] + 1;// 更新最短步数
                q.push({nx,ny}); // 将新的位置加入队列
            }
        }
    }
    return dis[0][0];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int x1,x2,y1,y2;
    cin>>x1>>y1>>x2>>y2;
    x1--,x2--,y1--,y2--; // 将坐标调整为0基索引
    cout<<bfs(x1,y1)<<endl;
    cout<<bfs(x2,y2);

    return 0;
}

注意将坐标调整为0基索引

原文地址：https://blog.csdn.net/Ct314/article/details/143868941

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！