我还在纳闷怎么找最长的距离。。。。
blutrex说枚举点对。
。。。。。我擦。。。。
blutrex好强！！！！！！！
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<cmath> #include<algorithm> #define maxv 905 #define maxe 180050 #define inf 0x7f7f7f7f using namespace std; int n,m,t,map[35][35],dis[35][35],ans=0; int dx[]={0,-1,0,1,0},dy[]={0,0,1,0,-1}; bool vis[35][35]; queue <int> q; char s[40]; bool judge(int x,int y) { if ((x>=1) && (x<=n) && (y>=1) && (y<=m)) return true; return false; } bool spfa(int sx,int sy) { while (!q.empty()) q.pop(); memset(vis,false,sizeof(vis)); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) dis[i][j]=inf; q.push(sx);q.push(sy);vis[sx][sy]=true;dis[sx][sy]=map[sx][sy]; while (!q.empty()) { int nowx=q.front();q.pop(); int nowy=q.front();q.pop(); vis[nowx][nowy]=false; for (int i=1;i<=4;i++) { int tx=nowx+dx[i],ty=nowy+dy[i]; if (judge(tx,ty)) { if (dis[tx][ty]>dis[nowx][nowy]+map[tx][ty]) { dis[tx][ty]=dis[nowx][nowy]+map[tx][ty]; if (!vis[tx][ty]) { vis[tx][ty]=true; q.push(tx);q.push(ty); } } } } } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { if (dis[i][j]<=t) ans=max(ans,(i-sx)*(i-sx)+(j-sy)*(j-sy)); } } int main() { scanf("%d%d%d",&n,&m,&t); for (int i=1;i<=n;i++) { scanf("%s",s); for (int j=1;j<=m;j++) map[i][j]=s[j-1]-'0'; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) spfa(i,j); double anss=sqrt(ans); printf("%.6lf ",anss); return 0; }