BFS百度(广度)优先搜索进阶

tkm2013 · 2024-07-14 13:22:13 · 算法·理论

噔噔噔噔！

广搜进阶它来了

本次的广搜会出现三维广搜和各种高难度的广搜

第一题D1298 Dungeon Master

这题从原本的二维广搜上升到了三维

然后原本的方向数组也要变为三个

int dh[6]={1,-1,0,0,0,0};
int dx[6]={0,0,-1,1,0,0};
int dy[6]={0,0,0,0,-1,1};

代码

#include<bits/stdc++.h>
#include<queue>
using namespace std;
int h,n,m;
int q_h,q_x,q_y,z_h,z_x,z_y;
int dis[35][35][35];
int dh[6]={1,-1,0,0,0,0};
int dx[6]={0,0,-1,1,0,0};
int dy[6]={0,0,0,0,-1,1};
bool check(int l,int x,int y){
    if(l<1 || x<1 || y<1 || l>h || x>n || y>m || dis[l][x][y]!=0){
        return 0;
    }
    return 1;
}
int bfs(int hh,int xx,int yy){
    queue<int> a,b,c;
    a.push(hh);b.push(xx);c.push(yy);
    while(!a.empty()){
        int l=a.front(),x=b.front(),y=c.front();
        a.pop();b.pop();c.pop();
        for(int i=0;i<6;i++){
            int zh=l+dh[i],zx=x+dx[i],zy=y+dy[i];
            if(check(zh,zx,zy)){
                a.push(zh);b.push(zx);c.push(zy);  
                dis[zh][zx][zy]=dis[l][x][y]+1;
                if(zh==z_h && zx==z_x && zy==z_y){
                    return dis[zh][zx][zy];
                } 
            }
        }
    }   
    return -1;
}
void work(){
    for(int i=1;i<=h;i++){
        for(int j=1;j<=n;j++){
            for(int l=1;l<=m;l++){
                dis[i][j][l]=0;
                char r;
                cin>>r;
                if(r=='#'){
                    dis[i][j][l]=-1;
                }
                if(r=='S'){
                    q_h=i;
                    q_x=j;
                    q_y=l;
                }
                if(r=='E'){
                    z_h=i;
                    z_x=j;
                    z_y=l;
                }
            }
        }
    }
    int k=bfs(q_h,q_x,q_y);
    if(k==-1){
        cout<<"Trapped!"<<endl;
    }else{
        printf("Escaped in %d minute(s).\n",k);
    }
}
int main(){
    while(cin>>h>>n>>m){
        if(h==0 && n==0 && m==0){
            return 0;
        }
        work();
    }
    return 0;
}

第二题

样例

这道题样例在广搜完后的bis数组为

图中-1为不可到点,非负整数位到那的最小拐弯次数

到终点的最短路径为

答案代码

#include<bits/stdc++.h>
#include<queue>
using namespace std;
int n,m;
int dis[1005][1005];
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
bool check(int x,int y){
    if(x<1 || y<1 || x>n || y>m || dis[x][y]!=0){
        return 0;
    }
    return 1;
}
void bfs(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    queue<int> xx,yy;
    xx.push(a);yy.push(b);
    while(!xx.empty()){
        int x=xx.front(),y=yy.front();
        xx.pop();yy.pop();
        for(int i=0;i<4;i++){
            int zx=x+dx[i],zy=y+dy[i];
            while(check(zx,zy)){
                xx.push(zx);yy.push(zy);  
                dis[zx][zy]=dis[x][y]+1;
                zx+=dx[i];zy+=dy[i]; 
            }
        }
    } 
    cout<<dis[c][d]-1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int r;
            cin>>r;
            if(r==1){
                dis[i][j]=-1;
            }
        }
    }
    bfs();
    return 0;
}