CF1749E双端队列BFS

· · 题解

看没有题解，就想着来交一发题解。

Sloution

看到这道题，首先可以想到两种方法，第一种是模拟出怪物的行动路线用仙人掌隔断，但复杂度令我不敢尝试，第二种就是bfs仙人掌的种植路线，也就是我接下来会讲的正解。

首先，仙人掌四联通格子不能同时种，所以bfs的方向只能是斜着的四个方向，然后题目要求种植的仙人掌要最少，所以肯定想到这条隔断上方的仙人掌路线要尽可能经过原本的仙人掌，所以就可以将到仙人掌格子的边权设为 0，到要种植仙人掌的格子的边权设为 1。此时我们的主角登场了，双端队列BFS，专门处理 01 边权的利器，用法也很好理解，就是将边权为 0 的放入队头，边权为 1 的放入队尾，思路结束。

建议练习板子题。 P4667 [BalticOI 2011 Day1]Switch the Lamp On

最后贴上代码

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
const int dx[]={0,0,1,-1,1,1,-1,-1};
const int dy[]={1,-1,0,0,1,-1,1,-1};
const int N=2e5+100;
struct xzh{
    int x,y;
};
vector<int>pre[N],dis[N];
string a[N];
deque<xzh>q;   
bool check(int x,int y){
    if(x<0||x>=n||y<0||y>=m)return false;
    for(int i=0;i<4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=0&&xx<n&&yy>=0&&yy<m&&a[xx][yy]=='#')return false;
    }
    return true;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)cin>>a[i];
        for(int i=0;i<n;i++)dis[i].clear(),pre[i].clear();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                dis[i].push_back(2e9);
                pre[i].push_back(0);
            }
        }
        for(int i=0;i<n;i++){
            if(a[i][0]=='#')q.push_front({i,0}),dis[i][0]=0;
            else if(check(i,0))q.push_back({i,0}),dis[i][0]=1;
        }
        while(!q.empty()){
            int x=q.front().x,y=q.front().y;
            q.pop_front();
            for(int i=4;i<8;i++){
                int xx=x+dx[i],yy=y+dy[i]; 
                if(!check(xx,yy))continue;
                int s=(a[xx][yy]=='.');
                if(dis[xx][yy]>dis[x][y]+s){
                    dis[xx][yy]=dis[x][y]+s;
                    pre[xx][yy]=i;
                    if(s)q.push_back({xx,yy});
                    else q.push_front({xx,yy});
                }
            }
        }
       int min_=2e9,minn;
        for(int i=0;i<n;i++){
            if(dis[i][m-1]<min_){
                min_=dis[i][m-1];minn=i;
            }
        }
        if(min_==2e9){
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        int x=minn,y=m-1;
        while(1){
            a[x][y]='#';
            if(!pre[x][y])break;
            int ls=pre[x][y];
            x-=dx[ls];y-=dy[ls];
        }
        for(int i=0;i<n;i++){
            cout<<a[i];
            printf("\n");
        }
    }
    return 0;
}