题目描述
windy有一块矩形土地，被分为 N*M 块 1*1 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子A不可以走到格子B，就没有距离。 如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。 如果windy可以移走T块障碍物，求所有格子间的最大距离。 保证移走T块障碍物以后，至少有一个格子不含有障碍物。
输入
输入文件maxlength.in第一行包含三个整数，N M T。 接下来有N行，每行一个长度为M的字符串，'0'表示空格子，'1'表示该格子含有障碍物。
输出
输出文件maxlength.out包含一个浮点数，保留6位小数。
样例输入
【输入样例一】 3 3 0 001 001 110 【输入样例二】 4 3 0 001 001 011 000 【输入样例三】 3 3 1 001 001 001
样例输出
【输出样例一】 1.414214 【输出样例二】 3.605551 【输出样例三】 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 。
题解
数据范围很小，考虑以每一个点为起点跑spfa，dis[i]记录i点到该点的最小障碍物，然后判断能否将这些障碍物删除，更新最大距离。
1 #include2 #include 3 #include 4 #include 5 #include 6 #define maxn 35 7 #define inf 1<<29 8 using namespace std; 9 queue q; 10 int dx[5]={ 0,0,1,-1},dy[5]={ 1,-1,0,0}; 11 int n,m,t,tot,a[maxn*maxn],head[maxn*maxn],vis[maxn*maxn],d[maxn*maxn],ecnt; 12 double ans; 13 char str[35]; 14 struct edge{ 15 int u,v,next; 16 }E[maxn*maxn*4]; 17 void addedge(int u,int v) 18 { 19 E[++ecnt].u=u; 20 E[ecnt].v=v; 21 E[ecnt].next=head[u]; 22 head[u]=ecnt; 23 } 24 int cal(int x,int y){ return m*(x-1)+y;} 25 bool ok(int x,int y) 26 { 27 if(x<=0||y<=0||x>n||y>m)return false; 28 return true; 29 } 30 void spfa(int x) 31 { 32 for(int i=1 ; i<=tot; ++i) 33 { 34 d[i]=inf; 35 vis[i]=0; 36 } 37 d[x]=a[x]; 38 vis[x]=1; 39 q.push(x); 40 while(!q.empty()) 41 { 42 int dd=q.front();q.pop(); 43 vis[dd]=0; 44 for(int i=head[dd] ; i ; i=E[i].next ) 45 { 46 int v=E[i].v; 47 if(d[v]>d[dd]+a[v]) 48 { 49 d[v]=d[dd]+a[v]; 50 if(!vis[v]) 51 { 52 vis[v]=1; 53 q.push(v); 54 } 55 } 56 } 57 } 58 } 59 void search(int x,int y,int xx,int yy) 60 { 61 int tmp=cal(xx,yy); 62 if(d[tmp]>t)return ; 63 ans=max(ans,sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y))); 64 } 65 int main() 66 { 67 scanf("%d%d%d",&n,&m,&t); 68 tot=n*m; 69 for(int i=1 ; i<=n ; ++i ) 70 { 71 scanf("%s",str); 72 for(int j=0;j