广搜提高①

_yang_yi_bo_ · 2024-08-01 13:24:37 · 算法·理论

P1746 离开中山路

广搜的模板题，直接套板子就行了。

#include<bits/stdc++.h>
using namespace std;
int n;
char c[1005][1005];
bool vis[1005][1005];
int sx,sy,ex,ey;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
struct kkk{
    int x,y,s;
};
int bfs(int sx,int sy,int ex,int ey){
    queue<kkk> q;
    q.push({sx,sy,0});
    vis[sx][sy]=1;
    while(!q.empty()){
        kkk u=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=u.x+dx[i],yy=u.y+dy[i],ss=u.s+1;
            if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&!vis[xx][yy]){
                vis[xx][yy]=1;
                q.push({xx,yy,ss});
                if(xx==ex&&yy==ey){
                    return ss;
                }
            }
        }
    }return -1;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>c[i][j];
            if(c[i][j]=='1'){
                vis[i][j]=1;
            }
        }
    }cin>>sx>>sy>>ex>>ey;
    cout<<bfs(sx,sy,ex,ey);
    return 0;
}

P6207 [USACO06OCT] Cows on Skates G

这一题是输出路径的问题，我们可以用一个 pre 数组存储每个点是从哪一个点转移过来的。

在走到终点后，我们可以递归输出路径，由于 pre 数组是存储上一个点，我们需要倒序输出，需要先递归，再输出。

#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[155][155];
bool vis[155][155];
int sx,sy,ex,ey;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
struct kkk{
    int x,y;
};
kkk pre[155][155];
void print(int x,int y){
    if(x==114514&&y==114514){
        return;
    }print(pre[x][y].x,pre[x][y].y);
    cout<<x<<" "<<y<<"\n";
}
void bfs(int sx,int sy,int ex,int ey){
    queue<kkk> q;
    q.push({sx,sy});
    vis[sx][sy]=1;
    pre[sx][sy].x=114514;
    pre[sx][sy].y=114514;
    while(!q.empty()){
        kkk u=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=u.x+dx[i],yy=u.y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){
                vis[xx][yy]=1;
                q.push({xx,yy});
                pre[xx][yy].x=u.x;
                pre[xx][yy].y=u.y;
                if(xx==ex&&yy==ey){
                    print(ex,ey);
                    return;
                }
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
            if(c[i][j]=='*'){
                vis[i][j]=1;
            }
        }
    }
    bfs(1,1,n,m);
    return 0;
}

P10234 [yLCPC2024] B. 找机厅

这题依然是用一个 pre 数组来存储上一个点，我们可以Ctrl+c,Ctrl+v把题解上一题的代码复制过来，进行一点小小的改变。

首先，不仅要判断有没有访问过，还有判断上一个格子与现在所在的格子是否不相同。

最后，输出步数后，递归函数里要根据上一个点与现在的点判断上次往哪个方向走。

#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[2005][2005];
bool vis[2005][2005];
int sx,sy,ex,ey;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int t;
struct kkk{
    int x,y,s;
};
kkk pre[2005][2005];
void print(int x,int y){
    if(x==114514&&y==114514){
        return;
    }print(pre[x][y].x,pre[x][y].y);
    if(pre[x][y].x==x&&pre[x][y].y==y+1){
        cout<<"L";
    }else if(pre[x][y].x==x&&pre[x][y].y==y-1){
        cout<<"R";
    }else if(pre[x][y].x==x+1&&pre[x][y].y==y){
        cout<<"U";
    }else if(pre[x][y].x==x-1&&pre[x][y].y==y){
        cout<<"D";
    }
}
void bfs(int sx,int sy,int ex,int ey){
    queue<kkk> q;
    q.push({sx,sy,0});
    vis[sx][sy]=1;
    pre[sx][sy].x=114514;
    pre[sx][sy].y=114514;
    while(!q.empty()){
        kkk u=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=u.x+dx[i],yy=u.y+dy[i],ss=u.s+1;
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&(c[xx][yy]=='1'&&c[u.x][u.y]=='0'||c[xx][yy]=='0'&&c[u.x][u.y]=='1')){
                vis[xx][yy]=1;
                q.push({xx,yy,ss});
                pre[xx][yy].x=u.x;
                pre[xx][yy].y=u.y;
                if(xx==ex&&yy==ey){
                    cout<<ss<<"\n";
                    print(ex,ey);
                    return;
                }
            }
        }
    }cout<<-1;
}
void work(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
            vis[i][j]=0;
            pre[i][j].x=0;
            pre[i][j].y=0;
        }
    }bfs(1,1,n,m);
    cout<<"\n";
}
int main(){
    cin>>t;
    while(t--){
        work();
    }
    return 0;
}

P10487 Nightmare II

这题要用到双向广搜，使用两个队列，一个存储男生所在的点，一个存储女生所在的点，并使用两个标记数组，一个标记男生走过的点，一个标记女生走过的点。

对于鬼魂，由于鬼魂会穿墙，所以鬼魂走到一个点走的步数为两点之间的曼哈顿距离，时间为 \lceil 两点之间的曼哈顿距离 \div 2\rceil。

注意 t 组数据，记得清空。

#include<bits/stdc++.h>
using namespace std;
char a[1005][1005];
int n,m,t;
struct kkk{
    int x,y,f;
};
bool vis[1005][1005][2];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
vector<kkk> op;
int sumt=0;
int dis(kkk a,kkk b){
    return abs(a.x-b.x)+abs(a.y-b.y);
}bool check1(int x,int y,int k){
    if(a[x][y]!='X'&&x>=1&&x<=n&&y>=1&&y<=m&&vis[x][y][k]==0){
        return true;
    }return false;
}bool check2(kkk a){
    for(int i=0;i<2;i++){
        if(dis(a,op[i])<=2*sumt){
            return false;
        }
    }return true;
}
queue<kkk> q1;
queue<kkk> q2;
int bfs(){
    while(!q1.empty()&&!q2.empty()){
        sumt++;
        int tot=3;
        while(tot--){
            int len=q1.size();
            while(len--){
                kkk u=q1.front();
                q1.pop();
                if(!check2(kkk{u.x,u.y})){
                    continue;
                }for(int i=0;i<4;i++){
                    int xx=u.x+dx[i];
                    int yy=u.y+dy[i];
                    if(check1(xx,yy,u.f)&&check2(kkk{xx,yy})){
                        vis[xx][yy][u.f]=1;
                        if(vis[xx][yy][!u.f]){
                            return sumt;
                        }q1.push(kkk{xx,yy,u.f});
                    }
                }
            }
        }tot=1;
        while(tot--){
            int len=q2.size();
            while(len--){
                kkk u=q2.front();
                q2.pop();
                if(!check2(kkk{u.x,u.y})){
                    continue;
                }for(int i=0;i<4;i++){
                    int xx=u.x+dx[i];
                    int yy=u.y+dy[i];
                    if(check1(xx,yy,u.f)&&check2(kkk{xx,yy})){
                        vis[xx][yy][u.f]=1;
                        if(vis[xx][yy][!u.f]){
                            return sumt;
                        }q2.push(kkk{xx,yy,u.f});
                    }
                }
            }
        }
    }return -1;
}
void init(){
    memset(vis,0,sizeof vis);
    while(!q1.empty()){
        q1.pop();
    }while(!q2.empty()){
        q2.pop();
    }op.clear();
    sumt=0;
}
int main(){
    cin>>t;
    while(t--){
        init();
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
                if(a[i][j]=='M'){
                    q1.push({i,j,0});
                    vis[i][j][0]=1;
                }else if(a[i][j]=='G'){
                    q2.push({i,j,1});
                    vis[i][j][1]=1;
                }else if(a[i][j]=='Z'){
                    op.push_back(kkk{i,j});
                }
            }
        }cout<<bfs()<<"\n";
    }
    return 0;
}

P2199 最后的迷宫

这一题同样是多组数据，要注意清空。

有两个坑点：

注意刚开始就能看到奖杯时，要直接输出 0；
注意起点与终点是反着输入的。

接着我们说一下思路。

由于这题 n 和 m 极限数据下都能达到 16384，不能使用普通数组，可以使用二维动态数组。

展示一下如何初始化二维动态数组：

a.resize(n);
for(int i=0;i<n;i++){
    a[i].resize(m);
}

如果习惯从一开始的话，可以将空间定义大一点。

另外，我们还可以使用一个 bool 数组来记录哈利能看到奖杯的地方，将有奖杯的地方向八个方向遍历即可。

#include<bits/stdc++.h>
using namespace std;
vector<vector<char> > a;
int n,m;
int sx,sy,ex,ey;
vector<vector<bool> > finish,vis;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int fx[8]={1,0,-1,0,1,1,-1,-1};
int fy[8]={0,1,0,-1,1,-1,1,-1};
struct kkk{
    int x,y,step;
};
void init(int ex,int ey){
    for(int i=0;i<8;i++){
        int x=ex,y=ey;
        while(true){
            if(x<1||y<1||x>n||y>m||a[x][y]=='X'){
                break;
            }finish[x][y]=1;
            x+=fx[i];
            y+=fy[i];
        }
    }
}
void bfs(int sx,int sy,int ex,int ey){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            finish[i][j]=0;
            vis[i][j]=0;
        }
    }init(ex,ey);
    queue<kkk> q;
    q.push({sx,sy,0});
    vis[sx][sy]=1;
    if(finish[sx][sy]==1){
        cout<<0<<"\n";
        return ;
    }
    while(!q.empty()){
        kkk u=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=u.x+dx[i],yy=u.y+dy[i],ss=u.step+1;
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&a[xx][yy]=='O'){
                q.push({xx,yy,ss});
                vis[xx][yy]=1;
                if(finish[xx][yy]==1){
                    cout<<ss<<"\n";
                    return;
                }
            }
        }
    }cout<<"Poor Harry\n";
}
int main(){
    cin>>n>>m;
    a.resize(n+5);
    finish.resize(n+5);
    vis.resize(n+5);
    for(int i=1;i<=n+3;i++){
        a[i].resize(m+5);
        finish[i].resize(m+5);
        vis[i].resize(m+5);
    }for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }while(true){
        cin>>ex>>ey>>sx>>sy;
        if(sx==0&&sy==0&&ex==0&&ey==0){
            return 0;
        }bfs(sx,sy,ex,ey);
    }
    return 0;
}