[SCOI2009]最长距离

• 分析：

  1. n，m范围都挺小的。那我们可以以每个点为起点，求出到达另外的点要移动的最少的障碍，然后枚举每一个

  点，只如果移动的障碍数在规定范围内，就求出他与起点的距离，取最大的一个

代码：

#include<bits/stdc++.h>

#define dl double

using namespace std;

const int N=35;

int n,m,t;
int a[N][N],dis[N][N];

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

inline int check(int x,int y)
{
    return x<1||x>n||y<1||y>m;
}

inline void dfs(int x,int y,int z)
{
    if(z>t) return ;
    if(dis[x][y]<=z) return ;
    dis[x][y]=z;

    for (int i=0;i<4;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(check(xx,yy)) continue;
        if(a[xx][yy]) dfs(xx,yy,z+1);
        else dfs(xx,yy,z);
    }
}

int main()
{
    cin>>n>>m>>t;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            char c;cin>>c;
            a[i][j]=c-'0';
        }

    dl ans=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            if(a[i][j]) continue;
            memset(dis,0x3f,sizeof(dis));
            dfs(i,j,0);

            for (int p=1;p<=n;p++)
                for (int k=1;k<=m;k++)
                    if(dis[p][k]<=t)
                        ans=max(ans,sqrt((dl)(p-i)*(dl)(p-i)+(dl)(k-j)*(dl)(k-j)));
        }

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

    return 0;
}