题解：CF2109F Penguin Steps

· · 题解

题目传送门

思路

首先这个 dis_M，直接二分+并查集即可。

然后我们先不考虑 dis_M 的限制，考虑怎么最大化 dis_F。

首先 dis_F 也可以二分。对于一个 x，考虑把 \ge x 的位置设成 1，其它位置设成 0。那么想让答案为 x 就要求操作后，1 形成了一堵墙，隔开了 (n,1) 和 (r,n)。

接下来就需要分类讨论了。

可以随便建造时，把每个位置的贡献暴力算出来，然后跑多源 dijkstra 就行。

不能随便建造就比较麻烦。首先有个显然的东西，M 留给 F 能建造墙的部分，留的格子越多墙的建造方式越多。所以我们要留尽可能多的格子。

这时 M 的走法就唯一了。否则我们假设有 2 条路径同时最优。那么如果这两条路径在中间部分无交，则一定有一条在另外一条上方，所以另一条不优；如果有交，每个无交的部分又回到了上一个情况。所以假设不成立。

然后这个最优路径，可以多源 bfs 出来。具体就是把第一行和最后一列终点上面的部分全加进队列，然后如果当前格子 >dis_M 就往八个方向扩展，否则什么也不干。

于是就只需要在 x\le dis_M 的基础上，不穿过最优路径即可（其实是不能经过多源 bfs 到过的点）。

代码

#include<bits/stdc++.h>
#define int long long
#define N 305
#define inf 2e9
#define mod 998244353
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int T=1,n,r,k,dism,disf,a[N][N],fa[N*N],b[N][N],dis[N][N];
int dx[8]={-1,-1,-1,0,1,1,1,0};
int dy[8]={-1,0,1,1,1,0,-1,-1};
char c[N][N];
bool vis[N][N],st[N][N];
struct node{
    int d,x,y;
    bool operator<(const node &t)const{
        return d>t.d;
    }
};
bool jud(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=n;
}
void init(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            vis[i][j]=0;
        }
    }
    queue<pii>q;
    for(int j=1;j<=n;j++){
        q.push({1,j});
        vis[1][j]=1;
    }
    for(int i=1;i<=r;i++){
        q.push({i,n});
        vis[i][n]=1;
    }
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        int x=t.x,y=t.y;
        if(a[x][y]<=dism)continue;
        for(int i=0;i<8;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(jud(tx,ty)&&!vis[tx][ty]){
                vis[tx][ty]=1;
                q.push({tx,ty});
            }
        }
    }
}
int id(int x,int y){
    return (x-1)*n+y;
}
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    x=find(x);y=find(y);
    if(x!=y)fa[x]=y;
}
bool check(int x){
    for(int i=1;i<=n*n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(j<n&&a[i][j]<=x&&a[i][j+1]<=x)merge(id(i,j),id(i,j+1));
            if(i<n&&a[i][j]<=x&&a[i+1][j]<=x)merge(id(i,j),id(i+1,j));
        }
    }
    return find(id(1,1))==find(id(r,n));
}
void dij(vector<pii>all,int op){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j]=inf;
            st[i][j]=0;
        }
    }
    priority_queue<node>q;
    for(auto it:all){
        dis[it.x][it.y]=b[it.x][it.y];
        q.push({dis[it.x][it.y],it.x,it.y});
    }
    while(!q.empty()){
        auto t=q.top();
        q.pop();
        int x=t.x,y=t.y;
        if(st[x][y])continue;
        st[x][y]=1;
        for(int i=0;i<8;i++){
            int tx=x+dx[i],ty=y+dy[i];
            if(jud(tx,ty)&&dis[tx][ty]>dis[x][y]+b[tx][ty]&&(op==0||!vis[tx][ty])){
                dis[tx][ty]=dis[x][y]+b[tx][ty];
                q.push({dis[tx][ty],tx,ty});
            }
        }
    }
}
bool check2(int x){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]>=x)b[i][j]=0;
            else{
                if(c[i][j]=='0')b[i][j]=inf;
                else b[i][j]=x-a[i][j];
            }
        }
    }
    if(x<=dism){
        vector<pii>all;
        int mn;
        for(int i=1;i<=n;i++){
            all.push_back({i,1});
        }
        dij(all,0);
        mn=inf;
        for(int j=1;j<=n;j++){
            mn=min(mn,dis[n][j]);
        }
        for(int i=r;i<=n;i++){
            mn=min(mn,dis[i][n]);
        }
        if(mn<=k)return 1;
        all.clear();
        mn=inf;
        for(int j=1;j<=n;j++){
            all.push_back({n,j});
        }
        dij(all,0);
        for(int i=1;i<=r;i++){
            mn=min(mn,dis[i][n]);
        }
        for(int j=1;j<=n;j++){
            mn=min(mn,dis[1][j]);
        }
        if(mn<=k)return 1;
        all.clear();
        mn=inf;
        for(int i=r;i<=n;i++){
            all.push_back({i,n});
        }
        dij(all,0);
        for(int j=1;j<=n;j++){
            mn=min(mn,dis[1][j]);
        }
        for(int i=1;i<=r;i++){
            mn=min(mn,dis[i][n]);
        }
        if(mn<=k)return 1;
        return 0;
    }
    else{
        vector<pii>all;
        int mn;
        for(int i=1;i<=n;i++){
            if(!vis[i][1])all.push_back({i,1});
        }
        dij(all,1);
        mn=inf;
        for(int j=1;j<=n;j++){
            if(!vis[n][j])mn=min(mn,dis[n][j]);
        }
        for(int i=r;i<=n;i++){
            if(!vis[i][n])mn=min(mn,dis[i][n]);
        }
        if(mn<=k)return 1;
        return 0;
    }
}
int get_m(){
    int l=1,r=1e6,res=1e6;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)){
            r=mid-1;
            res=mid;
        }
        else l=mid+1;
    }
    return res;
}
int get_f(){
    int l=1,r=2e6,res=1;
    while(l<=r){
        int mid=l+r>>1;
        if(check2(mid)){
            l=mid+1;
            res=mid;
        }
        else r=mid-1;
    }
    return res;
}
void solve(int cs){
    if(!cs)return;
    cin>>n>>r>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>c[i][j];
        }
    }
    dism=get_m();
    init();
    disf=get_f();
    cout<<dism<<' '<<disf<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // init();
    cin>>T;
    for(int cs=1;cs<=T;cs++){
        solve(cs);
    }
    return 0;
}