P4162题解

Nightsky_Stars · 2024-01-23 09:23:53 · 题解

思路：

给你一张 n \times m 的图，其中 a_{ij} = 1 表示有障碍，否则没有障碍，其中可以消除 t 个障碍，求所有格子的最大距离。

暴力建图+最短路

建完图后，去看哪个 d_i 小于 t，去算起点到的格子中心的距离，取个 \max 就行了。

#include<bits/stdc++.h>
using namespace std;
int d[50][50],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bool vis[50][50];
double ans=-1e9;
char a[50][50];
struct edge{
    int u,v,w;
};
vector<edge>e[50][50];
struct node{
    int sx,sy,val;
    bool operator<(const node &b) const{
        return val>b.val;
    }
};
priority_queue<node> q;
void dijkstra(int x,int y){
    memset(vis,0,sizeof(vis));
    memset(d,0x3f3f3f,sizeof(d));
    d[x][y]=0;
    q.push((node){x,y,0});
    while(q.empty()==0){
        int u=q.top().sx,v=q.top().sy;
        q.pop();
        if(vis[u][v]==1) continue;
        vis[u][v]=1;
        for(int i=0;i<e[u][v].size();i++){
            edge s=e[u][v][i];
            if(d[s.u][s.v]>d[u][v]+s.w){
                d[s.u][s.v]=d[u][v]+s.w;
                q.push((node){s.u,s.v,d[s.u][s.v]});
            }
        }
    }
    return ;
}
int main(){
    int n,m,t;
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=0;k<4;k++){
                int nx=i+dx[k],ny=j+dy[k];
                if(nx>=1&&nx<=n&&ny>=1&&ny<=m){//建图
                    int s;
                    if(a[nx][ny]=='1'){
                        s=1;
                    }else s=0;
                    e[i][j].push_back((edge){nx,ny,s});
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dijkstra(i,j);
            int s;
            if(a[i][j]=='1'){
                s=1;
            }else s=0;
            for(int k=1;k<=n;k++){
                for(int h=1;h<=m;h++){
                    if(k==i&&h==j) continue;
                    if(d[k][h]+s<=t) ans=max(ans,sqrt((k-i)*(k-i)+(h-j)*(h-j)));
                }
            }
        }
    }
    printf("%.6lf",ans);
    return 0;
}