Description
给定一个一定存在从起点到终点的路径的四联通迷宫。已知Tar左右方向移动的时间为1，上下移动的时间为未知实数v。求当Tar从起点到终点的最短移动时间为已知实数L时，未知实数v是多少。
输入数据包含多个测试点。第一行为一个整数T，表示测试点的数目。
对于每一个测试点，第一行包含实数L和两个整数R,C。R为迷宫的上下长度，C为迷宫的左右长度。
之后的R行，每行包含C个字符。其中空格表示空地，S表示起点，E表示终点，#表示围墙。
Output
对于每一个测试点，在单独的一行内输出未知实数v，输出保留5位小数。
2
2.5 4 5
#####
#S #
# E#
#####
21 13 12
############
#S## #E#
# ## # # #
# # # # #
### # # # #
# # # # #
# ## # # #
## # # # #
### # # # #
## # # # #
# ## # #
# # #
############
Sample Output
0.50000
0.21053
Data Constraint
20%的数据，1≤ R,C ≤ 10。
100%的数据，1≤ R,C ≤ 100，0≤ v <10。
思路
先用搜索找出s到e最短路径中走上下v和走左右的次数h，先设v为5.00000，得出时间t，因为h已经是固定的了，所以能改变的只有v，那么如果题目的l>t,v为5+(l-t)/v,否则v为5-(l-t)/v。
保留5位小数哦。
vara:array[0..1000,0..1000] of char;b:array[0..1000,0..1000] of real;f:array[0..1000,0..1000] of boolean;x1,s1,v,h,r,c:longint;l:real;
procedure main(x,y,z,s:longint);
beginif (x<=0)or(x>r)or(y<=0)or(y>c) then exit;if (z>v)and(s>h) then exit;if (s>l)and(h<>maxlongint) then exit;f[x,y]:=false;if (x=x1)and(y=s1) then begin v:=z;h:=s;end;if (f[x+1,y])and(b[x+1,y]=0)or(b[x,y]+2<b[x+1,y]) thenbeginb[x+1,y]:=b[x,y]+2;main(x+1,y,z+1,s);end;if (f[x-1,y])and(b[x-1,y]=0)or(b[x,y]+2<b[x-1,y]) thenbeginb[x-1,y]:=b[x,y]+2;main(x-1,y,z+1,s);end;if (f[x,y-1])and(b[x,y-1]=0)or(b[x,y]+1<b[x,y-1]) thenbeginb[x,y-1]:=b[x,y]+1;main(x,y-1,z,s+1);end;if (f[x,y+1])and(b[x,y+1]=0)or(b[x,y]+1<b[x,y+1]) thenbeginb[x,y+1]:=b[x,y]+1;main(x,y+1,z,s+1);end;f[x,y]:=true;
end;
vari,j,k,n,x,s:longint;mid,u:real;
beginassign(input,'maze.in');reset(input);assign(output,'maze.out');rewrite(output);readln(n);for i:=1 to n dobeginreadln(l,r,c);v:=maxlongint;h:=maxlongint;fillchar(f,sizeof(f),false);for j:=1 to r dobeginfor k:=1 to c dobeginread(a[j,k]);if a[j,k]<>'#' then f[j,k]:=true;if a[j,k]='S' thenbegin x:=j;s:=k;end;if a[j,k]='E' thenbegin x1:=j;s1:=k;end;end;readln;end;main(x,s,0,0);mid:=0.50000;fillchar(b,sizeof(b),0);u:=v*mid+h;if u>l thenmid:=mid-(u-l)/velse mid:=mid+(l-u)/v;writeln(mid:0:5);end;close(input);close(output);
end.