题意

给出n*m的图，每个格点为1或0，1代表到此格点是一个障碍物.在可以移除t块障碍物的条件下。
问所有互相可达的两点中，欧几里得距离最大的为多少。

题解

百度搜了一下原题数据范围才敢写....数据范围是<=30所以最多只有30*30=900个格点，可以求出每两点最少经过多少个障碍物后，枚举两点满足两点间障碍物<=t的最远距离。
求解每两点间建筑物可以对相邻点建图使用最短路堆优化dijkstra复杂度为

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 2e3 + 10;
const int mod = 1e9 + 7;

struct Edge{
   int to,cost,nxt;
}edges[maxn << 2];
int g[maxn][maxn];
int head[maxn];
int tot = 0;
int dis[maxn][maxn];
int n,m,T;
int vis[maxn];
int dir[4][2] = {0,1,1,0,0,-1,-1,0};

inline int id(int i,int j)
{
   return i * m + j;
}

void addedge(int u,int v,int w)
{
   edges[tot] = {v,w,head[u]};
   head[u] = tot++;
}

void dij(int s)
{
   dis[s][s] = g[s/m][s%m];
   vis[s] = 1;
   priority_queue<pii,vector<pii>,greater<> > pq;
   pq.push({0,s});
   while(!pq.empty()){
      pii hd = pq.top();
      pq.pop();
      for(int i = head[hd.second];i != -1;i = edges[i].nxt){
         int to = edges[i].to;
         int cost = edges[i].cost;
         if(vis[to]) continue;
         if(dis[s][to] > dis[s][hd.second] + cost){
            dis[s][to] = dis[s][hd.second] + cost;
            pq.push({dis[s][to],to});
            vis[to] = 1;
         } 
      }
   }
}

int dist(int a,int b)
{
   int x1 = a/m,x2 = b/m;
   int y1 = a%m,y2 = b%m;
   return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
}

int main()
{
   memset(head,-1,sizeof(head));
   tot = 0;
   scanf("%d%d%d",&n,&m,&T);
   getchar();
   for(int i = 0;i < n;++i){
      for(int j = 0;j < m;++j){
         char ch = getchar();
         g[i][j] = ch - '0';
      }
      getchar();
   }

   for(int i = 0;i < n;++i)for(int j = 0;j < m;++j){
      for(int k = 0;k < 4;++k){
         int nx = i + dir[k][0],ny = j + dir[k][1];
         if(nx >= 0 && nx < n && ny >= 0 && ny < m){
            int s = id(i,j),t = id(nx,ny);
            addedge(s,t,g[nx][ny]);
            addedge(t,s,g[i][j]);
         }
      }
   }

   for(int i = 0;i < n;++i)for(int j = 0;j < m;++j)
   for(int k = 0;k < n;++k)for(int l = 0;l < m;++l){
      int s = id(i,j),t = id(k,l);
      dis[s][t] = inf;
   }
   for(int i = 0;i < n;++i)
   for(int j = 0;j < m;++j)
   {
      memset(vis,0,sizeof(vis));
      dij(id(i,j));
   }
   int res = 0;
   for(int i = 0;i < n;++i)for(int j = 0;j < m;++j)
   for(int k = 0;k < n;++k)for(int l = 0;l < m;++l){
      int s = id(i,j),t = id(k,l);
      if(dis[s][t] <= T){
         res = max(res,dist(s,t));
      }
   }
   printf("%.6lf\n",sqrt(res));

   return 0;
}