【优先队列BFS】胖胖的牛牛

偏执的太偏执、 2024-03-24 11:44 26阅读 0赞

[1020-胖胖的牛牛\_2021秋季算法入门班第九章习题：图论（重现赛）@lamentropetion (nowcoder.com)][1020-_2021_lamentropetion _nowcoder.com]

题意：

![deb598120f0248059a578906f3019d02.png][]

思路：

**优先队列BFS，是指按照一定的权值排序的优先级对外进行BFS**

对于这道题，优先级是按最少需要转的次数来排序的

因此我们需要边扩展出去边计算转的次数，然后把次数放在优先队列里

那么，为了维护转动次数，我们还需要**给BFS升维**，即它的状态设计需要升维

**这里的状态设计和DP的状态设计思想是一样的，就是去考虑影响决策的因素和计算贡献需要什么值**

记录上次的坐标就行，这样就能维护转动次数了

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=5e2+10;
    const int mxe=3e3+10;
    struct ty{
        int x,y,prex,prey,dis;
        bool operator<(const ty&a)const{
            return a.dis<dis;
        }
    };
    
    priority_queue<ty> q;
    int n,sx,sy,ex,ey;
    int vis[mxn][mxn];
    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
    char G[mxn][mxn];
    bool check(int x,int y){
        return x>=1&&x<=n&&y>=1&&y<=n;
    }
    int bfs(){
        q.push({sx,sy,sx,sy,0});
        vis[sx][sy]=1;
        while(!q.empty()){
            ty u=q.top();
            q.pop();
            if(u.x==ex&&u.y==ey) return u.dis;
            vis[u.x][u.y]=1;
            for(int i=0;i<4;i++){
                int vx=u.x+dx[i],vy=u.y+dy[i];
                if(check(vx,vy)&&G[vx][vy]!='x'&&!vis[vx][vy]){
                    int add=0;
                    if(vx!=u.prex&&vy!=u.prey) add++;
                    q.push({vx,vy,u.x,u.y,u.dis+add});
                }
            }
        }
        return -1;
    }
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) cin>>G[i][j];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(G[i][j]=='A') sx=i,sy=j;
                if(G[i][j]=='B') ex=i,ey=j;
            }
        }
        //cout<<sx<<" "<<sy<<" "<<ex<<" "<<ey<<'\n';
        cout<<bfs()<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[1020-_2021_lamentropetion _nowcoder.com]: https://ac.nowcoder.com/acm/contest/54497/1020
[deb598120f0248059a578906f3019d02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/db4cc86e7ed245b8b71021980931911c.png