[SCOI2009]最长距离

题意

给你一的网格图，表示通路，为障碍。你有次机会使得障碍变为道路（变为）。求这张图上的最大欧几里得距离。

思路

先预处理表示一个点到任意点之间的障碍个数，如果小于则视为通路。再求这一点和全图的最大欧几里得距离。最后枚举全图每一个点作为起点的情况，再用记录最大值就可以了。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e3+5,INF=0x3f3f3f3f;
using namespace std;

int n,m,t;
int map_[N][N],dis[N][N],ans;
int mx[5]={-1,0,1,0},my[5]={0,-1,0,1};

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

void dfs(int x,int y,int sum)
{
    if(sum>t)    return ;
    if(sum>=dis[x][y]) return ;
    dis[x][y]=sum;
    for(int i=0;i<4;i++)
    {
        int xx=x+mx[i],yy=y+my[i];
        if(xx<=n&&xx>=1&&yy<=m&&yy>=1) dfs(xx,yy,sum+map_[xx][yy]);
    }
    return ;
}

int main()
{
    n=read();m=read();t=read();
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     {
         char opt;
         cin>>opt;
         map_[i][j]=opt-'0';
     }
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     {
         memset(dis,INF,sizeof(dis));
         int py;
         if(map_[i][j]==1) py=1;
         else py=0;
         dfs(i,j,py);
         for(int p=1;p<=n;p++)
          for(int y=1;y<=m;y++)
           if(dis[p][y]<=t)
            ans=max(ans,(p-i)*(p-i)+(y-j)*(y-j));
     }
    printf("%.6f",sqrt(ans));
    return 0;
}