BFS⑤

_yang_yi_bo_ · 2024-07-18 12:29:52 · 算法·理论

先来做一道签到题。

[ABC184E] Third Avenue

签到题是绿题。

这题是带费用的传送门，而且可以选择不进去。

由于可以选择不进传送门，所以需要标记传送门。

由于这是带费用的传送门，进入传送门时也相当于走了一步，需要将传送门放入队列。

我们只需在BFS的板子上处理一下传送门就行了。

处理传送门时，我们可以使用上次学的 vector<pair<int,int> >。

感觉不值绿题。

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[2005][2005];
bool vis[2005][2005];
int sx,sy,ex,ey;
vector<pair<int,int> > o[300];
struct kkk{
    int x,y,step;
};
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int bfs(){
    queue<kkk> q;
    vis[sx][sy]=1;
    q.push({sx,sy,0});
    while(!q.empty()){
        kkk u=q.front();
        q.pop();
        if(a[u.x][u.y]>='a'&&a[u.x][u.y]<='z'){
            char c=a[u.x][u.y];
            for(int i=0;i<o[c].size();i++){
                if((o[c][i].first!=u.x||o[c][i].second!=u.y)&&!vis[o[c][i].first][o[c][i].second]){
                    vis[o[c][i].first][o[c][i].second]=1;
                    q.push({o[c][i].first,o[c][i].second,u.step+1});
                    vis[o[c][i].first][o[c][i].second]=1;
                    if(o[c][i].first==ex&&o[c][i].second==ey){
                        return u.step+1;
                    }
                }
            }
        }
        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]){
                vis[xx][yy]=1;
                q.push({xx,yy,ss});
                if(xx==ex&&yy==ey){
                    return ss;
                }
            }
        }
    }return -1;
}
int main(){
    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]=='S'){
                sx=i;
                sy=j;
            }if(a[i][j]=='G'){
                ex=i;
                ey=j;
            }if(a[i][j]>='a'&&a[i][j]<='z'){
                o[a[i][j]].push_back(make_pair(i,j));
            }if(a[i][j]=='#'){
                vis[i][j]=1;
            }
        }
    }cout<<bfs()<<"\n";
    return 0;
}

Super Jaber

这道题的起点与终点不唯一，需要 q 此询问，可以想到需要预处理，而由于是迷宫问题，容易想到是用BFS预处理。

我们可以反向思考，从传送门出发，找每个点的最近距离。

最多 40 种颜色，当在使用颜色 k 的传送门时，答案是起点到 k 颜色的最短距离 + 终点到 k 颜色的最短距离。

那不使用传送门呢？还要跑一遍BFS吗？由于这题没有障碍物，最短距离为曼哈顿距离。

贴心给出曼哈顿距离的公式：

那么，如何求起点与终点到 k 颜色的最短距离呢？

excel大法好。

如图，我们要实现多个起点的BFS，也就是多源BFS。

实现方法很简单：将一堆起点一股脑塞入队列中，在正常进行BFS就行了。

给出可爱的代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k,q;
int a[1005][1005];
int dis[45][1005][1005];
bool flag[45];
struct kkk{
    int x,y,step;
};
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
vector<pair<int,int> > o[45];
void bfs(int x){
    queue<kkk> q;
    for(int i=1;i<=k;i++){
        flag[i]=0;
    }for(int i=0;i<o[x].size();i++){
        q.push({o[x][i].first,o[x][i].second,0});
        dis[x][o[x][i].first][o[x][i].second]=0;
    }while(!q.empty()){
        kkk u=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=u.x+dx[i];
            int yy=u.y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
                if(dis[x][xx][yy]>dis[x][u.x][u.y]+1){
                    q.push({xx,yy,u.step+1});
                    dis[x][xx][yy]=dis[x][u.x][u.y]+1;
                }
            }if(flag[a[u.x][u.y]]==0){
                flag[a[u.x][u.y]]=1;
                for(int i=0;i<o[a[u.x][u.y]].size();i++){
                    int xx=o[a[u.x][u.y]][i].first;
                    int yy=o[a[u.x][u.y]][i].second;
                    if(dis[x][xx][yy]>dis[x][u.x][u.y]+1){
                        q.push({xx,yy,u.step+1});
                        dis[x][xx][yy]=dis[x][u.x][u.y]+1;
                    }
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            o[a[i][j]].push_back(make_pair(i,j));
        }
    }memset(dis,0x3f,sizeof dis);
    for(int i=1;i<=k;i++){
        bfs(i);
    }cin>>q;
    while(q--){
        int sx,sy,ex,ey,cnt;
        cin>>sx>>sy>>ex>>ey;
        cnt=abs(sx-ex)+abs(sy-ey);
        for(int i=1;i<=k;i++){
            cnt=min(cnt,dis[i][sx][sy]+dis[i][ex][ey]+1);
        }cout<<cnt<<"\n";
    }
    return 0;
}