记录编号	38600	评测结果	AAAAAAAAAA
题目名称	[Violet 1] 迷宫花园	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.499 s
提交时间	2012-05-06 21:45:19	内存使用	0.42 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <utility>
#define MAXN 101
using namespace std;
const double zero=0.0000000;
const double ichi=1.0000000;
const double INF=1e9;
int Mat[MAXN][MAXN];
vector<int> Map[MAXN*MAXN];
int T,N,M,P;
int S,E;
double Time;
double L,R,Mid,Ans;
  
inline void AddEdge(int s,int e) {Map[s].push_back(e); Map[e].push_back(s);}
  
inline void init()
{
    string tmp;
    char c;  P=N*M;
    for(int i=1;i<=P;i++) Map[i].clear();
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            scanf("%c",&c);
            while(c!='#' && c!=' ' && c!='S' && c!='E') scanf("%c",&c);
            if(c=='#') {Mat[i][j]=0; continue;}
            if(c=='S') S=(i-1)*M+j; 
            if(c=='E') E=(i-1)*M+j;
            Mat[i][j]=1;
        } 
        getline(cin,tmp);
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            if(!Mat[i][j]) continue;
            /*往下*/
            if(i<N) {if(Mat[i+1][j]==1) AddEdge((i-1)*M+j,i*M+j);} 
            /*往右*/
            if(j<M) {if(Mat[i][j+1]==1) AddEdge((i-1)*M+j,(i-1)*M+j+1);}
        }
    }
    /*
    for(int i=1;i<=P;i++)
    {
        printf("%d ---> ",i);
        for(unsigned int j=0;j<Map[i].size();j++) printf("%d  ",Map[i][j]);
        printf("\n");
    }*/
}
/*
priority_queue<pair<double,int> >heap;
int flag[MAXN*MAXN];
double dist[MAXN*MAXN];
inline int dijkstra()
{
    int u,v; double nxt;
    for(int i=1;i<=P;i++) dist[i]=INF,flag[i]=0;
    dist[S]=zero; heap.push(make_pair(zero,S));
    while(!heap.empty())
    {
        u=heap.top().second; heap.pop();
        if(flag[u]) continue; flag[u]=1;
        for(unsigned int i=0;i<Map[u].size();i++)
        {
            v=Map[u][i];  if(u-v==M || v-u==M) nxt=dist[u]+Mid;
            else nxt=dist[u]+ichi; if(dist[v]>nxt) dist[v]=nxt;
            if(!flag[v]) heap.push(make_pair(-dist[v],v));
        }
    }
    if(dist[E]-0.00001==Time) return 2;
    return (dist[E]-0.00001<Time); 
}*/
  
inline int spfa()
{
    queue<int> qq;
    int flag[MAXN*MAXN];
    double dist[MAXN*MAXN];
    int u,v; double nxt;
    for(int i=1;i<=P;i++) dist[i]=INF,flag[i]=0;
    dist[S]=zero; qq.push(S); flag[S]=1;
    while(!qq.empty())
    {
        u=qq.front(); qq.pop(); flag[u]=0;
        for(unsigned int i=0;i<Map[u].size();i++)
        {
            v=Map[u][i]; if(u-v==M || v-u==M) nxt=dist[u]+Mid;
            else nxt=dist[u]+ichi; if(dist[v]>nxt) {dist[v]=nxt;
            if(!flag[v]) {flag[v]=1; qq.push(v);}}
        }
    }
    if(dist[E]-0.0000001==Time) return 2;
    return (dist[E]-0.0000001<Time); 
}
  
inline void binarysearch()
{
    Ans=zero;
    L=zero; R=10.0000000;
    int res;
    while(L+0.0000001<=R)
    {
        Mid=(L+R)/2;
        //res=dijkstra();
        res=spfa();
        if(res==2) {printf("%.5lf\n",Mid); return;}
        if(res==1) {L=Mid; Ans=Mid;}
        else R=Mid;
    }
    printf("%.5lf\n",Ans);
}
  
int main()
{
    freopen("mazev.in","r",stdin);
    freopen("mazev.out","w",stdout);
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
    {   
        scanf("%lf %d %d",&Time,&N,&M);
        init();
        binarysearch();
    }
    return 0;
}