[SCOI2009]最长距离

题意：
有一个n*m的地图，为1表示为有障碍物，你可以移走t个障碍物，求二个可以相互到达的点最大的欧几里德距离?

思路：
dfs暴力求出每一个点在移走t个障碍物后能到达的点，然后暴力求最大距离。

代码：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int d[35][35], dis[35][35], f[35][35], dx[4]= {1,0,0,-1}, dy[4]= {0,1,-1,0};

double ju(int x,int y,int a,int b)
{
    return sqrt((x-a)*(x-a)+(y-b)*(y-b));
}
int n, m;
void dfs(int x, int y, int t)
{
    if(t<0)
    {
        return ;
    }
    f[x][y]=t+1;
    dis[x][y]=1;
    for(int i=0; i<4; i++)
    {
        int a=x+dx[i], b=y+dy[i];
        if(a>=1&&b>=1&&a<=n&&b<=m&&(t>=f[a][b]||f[a][b]==-1))
        {
            dfs(a,b,t-d[a][b]);
        }
    }
}

int main()
{
    int t;
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            scanf("%1d",&d[i][j]);
        }
    }
    double ans=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(d[i][j]==1)
            {
                continue;
            }
            memset(f,-1,sizeof(f));
            memset(dis,0,sizeof(dis));
            dfs(i,j,t);
            for(int l=1; l<=n; l++)
            {
                for(int r=1; r<=m; r++)
                {
                    if(dis[l][r])
                        ans=max(ans,ju(i,j,l,r));
                }
            }
        }
    }
    printf("%.6f\n",ans);
    return 0;
}