直接二分这个v。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<cmath> #define maxn 150 #define maxv 10050 #define eps 1e-7 #define inf 2147483 using namespace std; int t,n,m,map[maxn][maxn],bx,by,ex,ey; int dx[]={0,1,-1,0,0},dy[]={0,0,0,1,-1}; double l,dis[maxn][maxn],lefts,rights; char s[maxn]; bool vis[maxn][maxn]; queue <int> q; bool judge(int x,int y) { if ((x>=1) && (x<=n) && (y>=1) && (y<=m) && (map[x][y])) return true; return false; } double spfa(double x) { while (!q.empty()) q.pop(); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) vis[i][j]=false,dis[i][j]=inf; q.push(bx);q.push(by);vis[bx][by]=true;dis[bx][by]=0; while (!q.empty()) { int hx,hy; hx=q.front();q.pop();hy=q.front();q.pop(); for (int i=1;i<=2;i++) { int nx=hx+dx[i],ny=hy+dy[i]; if ((judge(nx,ny) && (dis[nx][ny]>dis[hx][hy]+x))) { dis[nx][ny]=dis[hx][hy]+x; if (!vis[nx][ny]) { vis[nx][ny]=true; q.push(nx);q.push(ny); } } } for (int i=3;i<=4;i++) { int nx=hx+dx[i],ny=hy+dy[i]; if ((judge(nx,ny) && (dis[nx][ny]>dis[hx][hy]+1))) { dis[nx][ny]=dis[hx][hy]+1; if (!vis[nx][ny]) { vis[nx][ny]=true; q.push(nx);q.push(ny); } } } vis[hx][hy]=false; } return dis[ex][ey]; } void work() { scanf("%lf%d%d ",&l,&n,&m); for (int i=1;i<=n;i++) { gets(s); for (int j=0;j<m;j++) { if (s[j]=='#') map[i][j+1]=0; else if (s[j]==' ') map[i][j+1]=1; else if (s[j]=='S') {bx=i;by=j+1;map[bx][by]=1;} else {ex=i;ey=j+1;map[ex][ey]=1;} } } lefts=0;rights=10;double ans,ret; while (rights-lefts>eps) { double mid=(lefts+rights)/2; ans=spfa(mid);ret=mid; if (ans>=l) rights=mid; else lefts=mid; } printf("%.5lf ",ret); } int main() { scanf("%d",&t); for (int i=1;i<=t;i++) work(); return 0; }