【多维BFS】迷宫

港控/mmm° 2024-03-24 12:24 51阅读 0赞

**直接1A，爽了**

[1007-迷宫\_2021秋季算法入门班第六章习题：搜索与搜索剪枝（重现赛）@lamentropetion (nowcoder.com)][1007-_2021_lamentropetion _nowcoder.com]

题意：

![a8a60e77fbc84df6b97123fa6eff74d2.png][]

思路：

搜索题一般和DP的步骤很像

先去状态设计：

在遇到门的时候，是否有钥匙成了决策的影响因素

因此需要加一维来记录是否有钥匙

(x,y,k)表示在坐标(x,y)有无钥匙，有就是1，没有就是0

然后去普通的BFS就行了，注意对可能遇到的情况进行小分类讨论

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=5e2+10;
    const int mxe=3e3+10;
    struct ty{
        int x,y,k;
    };
    
    queue<ty> q;
    string s[mxn];
    int n,m,sx,sy,ex,ey;
    int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
    int vis[mxn][mxn][2],dis[mxn][mxn][2];
    bool check(int x,int y){
        return x>=1&&x<=n&&y>=1&&y<=m;
    }
    int F(int x){
        if(x==0) return 1;
        return 0;
    }
    void bfs(){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        q.push({sx,sy,0});
        vis[sx][sy][0]=1;
        dis[sx][sy][0]=0;
        while(!q.empty()){
            ty u=q.front();
            q.pop();
            if(s[u.x][u.y]=='E') break;
            for(int i=0;i<4;i++){
                int vx=u.x+dx[i],vy=u.y+dy[i];
                if(check(vx,vy)&&!vis[vx][vy][u.k]){
                    if(s[vx][vy]=='.'||s[vx][vy]=='E'){
                        if(dis[vx][vy][u.k]>dis[u.x][u.y][u.k]+1) dis[vx][vy][u.k]=dis[u.x][u.y][u.k]+1,q.push({vx,vy,u.k});
                    }else if(s[vx][vy]=='K'){
                        if(u.k==0){
                            if(dis[vx][vy][F(u.k)]>dis[u.x][u.y][u.k]+1) dis[vx][vy][F(u.k)]=dis[u.x][u.y][u.k]+1,q.push({vx,vy,F(u.k)});
                        }else{
                            if(dis[vx][vy][u.k]>dis[u.x][u.y][u.k]+1) dis[vx][vy][u.k]=dis[u.x][u.y][u.k]+1,q.push({vx,vy,u.k});
                        }
                    }else if(s[vx][vy]=='D'){
                        if(u.k==1&&dis[vx][vy][u.k]>dis[u.x][u.y][u.k]+1) dis[vx][vy][u.k]=dis[u.x][u.y][u.k]+1,q.push({vx,vy,u.k});
                    }else if(s[vx][vy]=='S'){
                        if(dis[vx][vy][u.k]>dis[u.x][u.y][u.k]+1) dis[vx][vy][u.k]=dis[u.x][u.y][u.k]+1,q.push({vx,vy,u.k});
                    }
                }
            }
        }
    }
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>s[i],s[i]=" "+s[i];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(s[i][j]=='S') sx=i,sy=j;
                if(s[i][j]=='E') ex=i,ey=j;
            }
        }
        bfs();
        /*for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(dis[i][j][1]==0x3f3f3f3f) cout<<'*'<<" \n"[j==m];
                else cout<<dis[i][j][1]<<" \n"[j==m];
            }
        }*/
        int ans=min(dis[ex][ey][0],dis[ex][ey][1]);
        if(ans==0x3f3f3f3f) cout<<-1<<'\n';
        else cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[1007-_2021_lamentropetion _nowcoder.com]: https://ac.nowcoder.com/acm/contest/54516/1007
[a8a60e77fbc84df6b97123fa6eff74d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/41343938528a4bbf9abf071e706d3cca.png