[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; }
