[SCOI2009]最长距离

Description

点击查看题面

windy有一块矩形土地，被分为 NM 块 11 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子A不可以走到格子B，就没有距离。 如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。 如果windy可以移走T块障碍物，求所有格子间的最大距离。 保证移走T块障碍物以后，至少有一个格子不含有障碍物。

输入格式
第一行包含三个整数，N M T。 接下来有N行，每行一个长度为M的字符串，'0'表示空格子，'1'表示该格子含有障碍物。

输出格式
包含一个浮点数，保留6位小数。

输入输出样例
输入 #1
3 3 0
001
001
110
输出 #1
1.414214

输入 #2
4 3 0
001
001
011
000
输出 #2
3.605551

输入 #3
3 3 1
001
001
001
输出 #3
2.828427
说明/提示
20%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 0 。

40%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 2 。

100%的数据，满足 1 <= N,M <= 30 ； 0 <= T <= 30 。

Problem solving

这道题的意思就是有一个的图，某些点存在障碍，问你在移走最多个障碍物之后，可以达到的最大的两点间距离，若两点有公共边且都没有障碍，两点可达。
我们可以发现，问题的关键在于障碍物的处理。因为我们只需要找两点之间的最大距离，所以这个障碍物全都用来满足最大距离的情况就行了。
建图，把有障碍的地方距离建为，其它可达的建为。然后对于每个点，我们用（或者）求出其他点到它的最短距离，如果最短距离小于等于，说明我们可以通过移走障碍物把这两个点联通。然后更新一下最大值即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 35;
const int  INF = 0x3f3f3f3f;
#define mp make_pair
#define pii pair<int,int>
string s[N];
int n,m,k,dis[N][N],vis[N][N],d[4][2]={1,0,0,1,-1,0,0,-1};
void spfa(int x,int y){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dis[i][j]=INF;
            vis[i][j]=0;
        }
    }
    queue<pii> q;
    q.push(mp(x,y));
    vis[x][y]=1;dis[x][y]=(s[x][y]=='1');
    while(!q.empty()){
        pii mid=q.front();q.pop();
        x=mid.first,y=mid.second;
        vis[x][y]=0;
        for(int i=0;i<4;i++){
            int dx=x+d[i][0],dy=y+d[i][1];
            if(dx<0||dx>=n||dy<0||dy>=m)    continue;
            if(dis[dx][dy]>dis[x][y]+(s[dx][dy]=='1')){
                dis[dx][dy]=dis[x][y]+(s[dx][dy]=='1');
                q.push(mp(dx,dy));
                vis[dx][dy]=1;
            }
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<n;i++)    cin>>s[i];
    double ans=0;
    for(int a=0;a<n;a++){
        for(int b=0;b<m;b++){
            spfa(a,b);
            for(int c=0;c<n;c++){
                for(int d=0;d<m;d++){
                    if(dis[c][d]<=k){
                        ans=max(ans,sqrt((a-c)*(a-c)+(b-d)*(b-d)));
                    }
                }
            }
        }
    }
    printf("%.6lf\n",ans);
    return 0;
}
赏