【BZOJ 1295】 [SCOI2009]最长距离

1295: [SCOI2009]最长距离Time Limit:10 SecMemory Limit:162 MBSubmit:945Solved:492[Submit][Status][Discuss]Description

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

Input

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

Output

输出文件maxlength.out包含一个浮点数，，保留6位小数。

Sample Input

【输入样例一】3 3 0001001110【输入样例二】4 3 0001001011000【输入样例三】3 3 1001001001

Sample Output

【输出样例一】1.414214【输出样例二】3.605551【输出样例三】2.828427

HINT

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

Source

Day2

spfa+暴力。

对于每一个格子，用spfa预处理出他到任何一个格子的至少要移除几个障碍。

然后暴力枚举需要移除障碍<=t的格子，输出最大距离。

#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#define M 900000+5#define pa pair<int,int>#define mp make_pair#include <queue>#define inf 0x3f3f3f3fusing namespace std;struct data{double dis;int need;}r[M];char s[100];int f[5][3],tot=0,d[35][35],inq[35][35],n,m,t,a[35][35];queue<pa> q;double dis[35][35][35][35];int C(int x,int y){return (x-1)*m+y;}bool ok(int x,int y){if (x<1||y<1||x>n||y>m) return false;return true;}void spfa(int x,int y){for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)d[i][j]=inf,inq[i][j]=0;d[x][y]=a[x][y];q.push(mp(x,y));inq[x][y]=1;while (!q.empty()){pa p=q.front();q.pop();int xx=p.first,yy=p.second;inq[xx][yy]=0;for (int i=1;i<=4;i++){int nx=xx+f[i][1],ny=yy+f[i][2];if (ok(nx,ny)&&d[xx][yy]+a[nx][ny]<d[nx][ny]){d[nx][ny]=d[xx][yy]+a[nx][ny];if (!inq[nx][ny])inq[nx][ny]=1,q.push(mp(nx,ny));}}}for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)r[++tot].dis=dis[i][j][x][y],r[tot].need=d[i][j];}bool cmp(data a,data b){return a.dis>b.dis;}int main(){f[1][1]=f[2][1]=0,f[1][2]=1,f[2][2]=-1;f[3][2]=f[4][2]=0,f[3][1]=1,f[4][1]=-1;scanf("%d%d%d",&n,&m,&t);for (int i=1;i<=n;i++){scanf("%s",1+s);for (int j=1;j<=m;j++)a[i][j]=s[j]-'0';}for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)for (int x=1;x<=n;x++)for (int y=1;y<=m;y++)dis[i][j][x][y]=sqrt((double)(x-i)*(x-i)+(y-j)*(y-j));for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)spfa(i,j);sort(r+1,r+1+tot,cmp);for (int i=1;i<=tot;i++)if (r[i].need<=t){printf("%.6lf\n",r[i].dis);return 0;}return 0;}

因为你的喜爱会挡也挡不住地流露出来。