Description：

一块矩形土地分为 $ N\times M $ 块 $ 1\times 1 $ 的小格子。有的格子含有障碍物。如果从格子 $A$ 可以走到格子 $B$ ，那么两个格子的距离就为两个格子中心的欧几里德距离。可以移走 $T$ 块障碍物，求所有格子间的最大距离。

$1\le n,m,t\le 30$

Solution：

看这个数据范围并没有什么思路，而欧几里得距离非常不好转化，所以直接求最大距离是肯定求不出来的。

直接求求不出来，而数据范围又不大，由于最后成为答案的一定是一对点对，我们可以把问题转化为有哪些点对可以在移走 $T$ 块障碍物的情况下联通，最后再暴力更新答案。

到这里已经就是正解了，只要用 $SPFA$ 求出从 $i$ 到 $j$ 最少经过障碍物的最小值 $d[i][j]$ 就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

inline int getc()

{

	register char c = getchar();

	while(c != '0' && c != '1')c = getchar();

	return c - '0';

}

int n,m,t;

#define MAXN 31

int a[MAXN][MAXN];

int d[MAXN][MAXN][MAXN][MAXN];

bool v[MAXN][MAXN];

#define fi first

#define se second

int mx[4] = {0,0,1,-1};

int my[4] = {1,-1,0,0};

void SPFA(int x,int y)

{

	d[x][y][x][y] = a[x][y];

	queue< pair<int,int> > q;q.push(make_pair(x,y));

	memset(v,false,sizeof(v));

	while(!q.empty())

	{

		pair<int,int> k = q.front();q.pop();

		v[k.fi][k.se] = false;

		for(int i = 0;i < 4;++i)

		{

			int nx = k.fi + mx[i],ny = k.se + my[i];

			if(nx < 1 || nx > n || ny < 1 || ny > m)continue;

			if(d[x][y][nx][ny] > d[x][y][k.fi][k.se] + a[nx][ny])

			{

				d[x][y][nx][ny] = d[x][y][k.fi][k.se] + a[nx][ny];

				if(!v[nx][ny])

				{

					v[nx][ny] = true;

					q.push(make_pair(nx,ny));

				}

			}

		}

	}

	return;

}

int main()

{

	scanf("%d%d%d",&n,&m,&t);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			a[i][j] = getc();

	memset(d,0x3f,sizeof(d));

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			SPFA(i,j);

	double ans = 0;

	for(int i1 = 1;i1 <= n;++i1)for(int j1 = 1;j1 <= m;++j1)

		for(int i2 = 1;i2 <= n;++i2)for(int j2 = 1;j2 <= m;++j2)

			if(d[i1][j1][i2][j2] <= t)

				ans = max(ans,sqrt((i1 - i2) * (i1 - i2) + (j1 - j2) * (j1 - j2)));

	printf("%.6lf\n",ans);

	return 0;

}