[SCOI2009]最长距离

100%的数据,满足1<=N,M<=30,0<=T<=30---来自洛谷的数据范围.
简单来说就是暴力,暴力枚举一个点,然后再算到其他点的之间最少需要移除多少障碍物.然后就结束了.

#include <bits/stdc++.h>
using namespace std;
const int N=32;
char s[N][N];
int n,m,t,w[N][N],dis[N][N];
int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
void dfs(int x,int y,int cnt)
{
    //cout<<x<<' '<<y<<endl;
    if(cnt>=dis[x][y])    return;
    if(cnt>t)            return;
    dis[x][y]=cnt;
    for(int i=0;i<4;i++)
    {
        int tx=x+dx[i],ty=y+dy[i];
        if(tx>=1&&tx<=n&&ty>=1&&ty<=m)    dfs(tx,ty,cnt+w[tx][ty]);
    }
}

int main()
{
    int ans=0;
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>s[i][j];
            w[i][j]=s[i][j]-'0';
        }
    }
    for(int h1=1;h1<=n;h1++)
    {
        for(int l1=1;l1<=m;l1++)
        {
            memset(dis,0x3f,sizeof dis);
            int sum;
            w[h1][l1]==1?sum=1:sum=0;
            dfs(h1,l1,sum);
            for(int h2=1;h2<=n;h2++)
            {
                for(int l2=1;l2<=m;l2++)
                {
                    if(dis[h2][l2]<=t)
                    {
                        ans=max(ans,(h2-h1)*(h2-h1)+(l2-l1)*(l2-l1));
                    }
                }
            }
        }
    }
    printf("%.6lf\n",sqrt(ans));
    return 0;
}