1 /*  2 分析：符合二分的原理：当v变大，dis一定变大，而且v的具体范围很小，才是0--10，符合二分原理。  3 二分出一个V，就用spfa求一次最短路，看看最短的长度与L大小关系，以此来二分。  4 */  5 #include<cmath>  6 #include<iostream>  7 using namespace std;  8 #include<cstdio>  9 #include<queue> 10 #include<cstring> 11 #define R 110 12 int T,r,c; 13 bool inque[R*R]; 14 char ditu[R][R]; 15 double L,z,y; 16 double dist[R*R]; 17 int head[10010],bh=0,sta,endd,bhh[R][R]; 18 struct Edge{ 19     int v,last; 20     double w; 21 }edge[40005]; 22 int t=0; 23 void input() 24 { 25     scanf("%lf%d%d\n",&L,&r,&c); 26     for(int i=1;i<=r;++i) 27     { 28         for(int j=1;j<=c;++j) 29         { 30             scanf("%c",&ditu[i][j]); 31             if(ditu[i][j]==32)  32             { 33                 bh++; 34                 bhh[i][j]=bh; 35             } 36             if(ditu[i][j]==‘S‘)bhh[i][j]=sta=++bh; 37             if(ditu[i][j]==‘E‘)bhh[i][j]=endd=++bh; 38          }  39         scanf("\n"); 40      }  41        42 } 43 void add_edge(int i,int j) 44 { 45     if(i-1>0&&ditu[i-1][j]!=‘#‘) {++t;edge[t].v=bhh[i-1][j];edge[t].w=-1;edge[t].last=head[bhh[i][j]];head[bhh[i][j]]=t;} 46     if(i<r&&ditu[i+1][j]!=‘#‘)   {++t;edge[t].v=bhh[i+1][j];edge[t].w=-1;edge[t].last=head[bhh[i][j]];head[bhh[i][j]]=t;} 47     if(j-1>0&&ditu[i][j-1]!=‘#‘) {++t;edge[t].v=bhh[i][j-1];edge[t].w=1;edge[t].last=head[bhh[i][j]];head[bhh[i][j]]=t;} 48     if(j<c&&ditu[i][j+1]!=‘#‘)   {++t;edge[t].v=bhh[i][j+1];edge[t].w=1;edge[t].last=head[bhh[i][j]];head[bhh[i][j]]=t;} 49 } 50 void build_tu() 51 { 52    for(int i=1;i<=r;++i) 53      for(int j=1;j<=c;++j) 54      if(ditu[i][j]!=‘#‘)  55      { 56          add_edge(i,j);     57      } 58 } 59 double SPFA(double ww) 60 { 61     for(int i=1;i<=bh;++i) 62       dist[i]=(1<<30)-1; 63     dist[sta]=0; 64     memset(inque,false,sizeof(inque)); 65     queue<int>Q; 66     Q.push(sta); 67     inque[sta]=true; 68     while(!Q.empty()) 69     { 70         int nowt=Q.front(); 71         Q.pop(); 72         inque[nowt]=false; 73         for(int l=head[nowt];l;l=edge[l].last) 74         { 75             if(edge[l].w<0) 76             { 77                 if(dist[edge[l].v]>dist[nowt]+ww) 78                 { 79                     dist[edge[l].v]=dist[nowt]+ww; 80                     if(!inque[edge[l].v]) 81                     { 82                         inque[edge[l].v]=true; 83                         Q.push(edge[l].v); 84                     } 85                 } 86             } 87             else { 88                 if(dist[edge[l].v]>dist[nowt]+edge[l].w) 89                 { 90                     dist[edge[l].v]=dist[nowt]+edge[l].w; 91                     if(!inque[edge[l].v]) 92                     { 93                         inque[edge[l].v]=true; 94                         Q.push(edge[l].v); 95                     } 96                 } 97             } 98         } 99     }100     return dist[endd];101 }102 int main()103 {104     cin>>T;105     while(T--)106     {107       input();108       build_tu();109       z=0;y=10;110       while(z<=y)111       {112           double mid=(z+y)/2;113           double ans=SPFA(mid);114           if(ans>=L) y=mid-0.000001;/*注意这里要加0.000001，之前的二分加1，是为了去一个区间（int），但是现在是double，所以要+0115 .000001。*/116           else z=mid+0.000001;117       }118       printf("%0.5lf\n",y);119     }120     121     return 0;122 }