记录编号	153635	评测结果	AAAAAAAAAA
题目名称	[Violet 1] 迷宫花园	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.789 s
提交时间	2015-03-18 16:09:53	内存使用	0.49 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const long long int INF=1e15,DIS=100000000;
int addx[4]={0,0,1,-1};
int addy[4]={1,-1,0,0};
long long dis[101][101]={0};
bool MAP[101][101]={0},flag[101][101]={0};
int i,p,n,m,T,ux,uy,vx,vy,x,y;
long long l,r,mid,ans,V,temp;

int quex[10050]={0},qheadx=1,qtailx=0;
inline int GETx(){int X=quex[qheadx];quex[0]--;if(++qheadx==10050)qheadx=1;return X;}
inline void PUSHx(int X){quex[0]++;if(++qtailx==10050)qtailx=1;quex[qtailx]=X;}

int quey[10050]={0},qheady=1,qtaily=0;
inline int GETy(){int Y=quey[qheady];quey[0]--;if(++qheady==10050)qheady=1;return Y;}
inline void PUSHy(int Y){quey[0]++;if(++qtaily==10050)qtaily=1;quey[qtaily]=Y;}

double v;
char ch;
void init()
{
	memset(MAP,0,sizeof(MAP));
	scanf("%lf%d%d",&v,&n,&m);
	for(i=1;i<=n;i++)
	{
		while((ch=getchar())!='\n');
		for(p=1;p<=m;p++)
		if((ch=getchar())==' ')MAP[i][p]=1;
		else if(ch=='S')MAP[i][p]=1,ux=i,uy=p;
		else if(ch=='E')MAP[i][p]=1,vx=i,vy=p;
	}
	V=v*DIS;
}

inline int spfa()
{
	memset(flag,0,sizeof(flag));
	PUSHx(ux);PUSHy(uy);flag[ux][uy]=1;
	while(quex[0])
	{
		x=GETx(),y=GETy(),dis[x][y]=INF;
		if(x>1&&MAP[x-1][y]&&!flag[x-1][y])flag[x-1][y]=1,PUSHx(x-1),PUSHy(y);
		if(x<n&&MAP[x+1][y]&&!flag[x+1][y])flag[x+1][y]=1,PUSHx(x+1),PUSHy(y);
		if(y>1&&MAP[x][y-1]&&!flag[x][y-1])flag[x][y-1]=1,PUSHx(x),PUSHy(y-1);
		if(y<m&&MAP[x][y+1]&&!flag[x][y+1])flag[x][y+1]=1,PUSHx(x),PUSHy(y+1);
	}
	memset(flag,0,sizeof(flag));
	PUSHx(ux);PUSHy(uy);flag[ux][uy]=1;dis[ux][uy]=0;
	while(quex[0])
	{
		x=GETx(),y=GETy();flag[x][y]=0;
		if(x>1&&MAP[x-1][y]&&dis[x-1][y]>dis[x][y]+ans)
		{dis[x-1][y]=dis[x][y]+ans;if(!flag[x-1][y])flag[x-1][y]=1,PUSHx(x-1),PUSHy(y);}
		
		if(x<n&&MAP[x+1][y]&&dis[x+1][y]>dis[x][y]+ans)
		{dis[x+1][y]=dis[x][y]+ans;if(!flag[x+1][y])flag[x+1][y]=1,PUSHx(x+1),PUSHy(y);}
		
		if(y>1&&MAP[x][y-1]&&dis[x][y-1]>dis[x][y]+DIS)
		{dis[x][y-1]=dis[x][y]+DIS;if(!flag[x][y-1])flag[x][y-1]=1,PUSHx(x),PUSHy(y-1);}
		
		if(y<m&&MAP[x][y+1]&&dis[x][y+1]>dis[x][y]+DIS)
		{dis[x][y+1]=dis[x][y]+DIS;if(!flag[x][y+1])flag[x][y+1]=1,PUSHx(x),PUSHy(y+1);}
	}
	if(dis[vx][vy]<V)return 1;
	if(dis[vx][vy]>V)return 2;
	return 3;
}
void work()
{
	l=0,r=DIS*10;
	while(l<r)
	{
		ans=mid=(l+r)>>1;
		temp=spfa();
		if(temp==1)l=mid+1;
		else if(temp==2)r=mid-1;
		else break;
	}
	v=ans;v/=DIS;
	printf("%.5lf\n",v);
}
int main()
{
	freopen("mazev.in","r",stdin);
	freopen("mazev.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		init();
		work();
	}
	return 0;
}