| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
帮我看看,,,TLE!!--pascalconst dx1:array[1..4]of -1..1=(0,-1,0,1);
dy1:array[1..4]of -1..1=(-1,0,1,0);
dx2:array[1..4]of -1..1=(1,0,-1,0);
dy2:array[1..4]of -1..1=(0,1,0,-1);
var xy:array[0..40,1..2]of integer;
xx:array[0..40,0..40]of longint;
w,h,xs,ys,xe,ye,ans,ok,ook:integer;
a,b:array[0..40,0..40]of 0..1;
procedure init;
var s:string;
i,j:integer;
begin
readln(h,w);
fillchar(a,sizeof(a),0);
for i:=1 to w do
begin
readln(s);
for j:=1 to h do
begin
case s[j]of
'.':a[i,j]:=1;
'S':begin xs:=i;ys:=j;end;
'E':begin a[i,j]:=1;xe:=i;ye:=j;end;
end;
b[i,j]:=a[i,j];
end;
end;
end;
procedure dfs1(x1,y1:integer);
var i,x,y:integer;
begin
for i:=1 to 4 do
begin
x:=x1+dx1[i];y:=y1+dy1[i];
if a[x,y]=1 then
begin
a[x,y]:=0;
inc(ans);
if(x=xe)and(y=ye)then exit else
begin
dfs1(x,y);
if a[xe,ye]=0 then exit;
a[x,y]:=1;
inc(ans);
end;
end;
end;
end;
procedure dfs2(x1,y1:integer);
var i,x,y:integer;
begin
for i:=1 to 4 do
begin
x:=x1+dx2[i];y:=y1+dy2[i];
if b[x,y]=1 then
begin
b[x,y]:=0;
inc(ans);
if(x=xe)and(y=ye)then exit else
begin
dfs2(x,y);
if b[xe,ye]=0 then exit;
b[x,y]:=1;
inc(ans);
end;
end;
end;
end;
procedure bfs;
var i,j,open,closed,x,y:integer;
procedure pd(x2,y2:integer);
begin
if (a[x2,y2]=1)and(xx[x2,y2]=0) then
begin
inc(closed);
xy[closed,1]:=x2;xy[closed,2]:=y2;
xx[x2,y2]:=xx[x,y]+1;
end;
end;
begin
fillchar(xx,sizeof(xx),0);
fillchar(xy,sizeof(xy),0);
open:=0;closed:=1;xy[1,1]:=xs;xy[1,2]:=ys;xx[xs,ys]:=1;
repeat
inc(open);
x:=xy[open,1];y:=xy[open,2];
pd(x-1,y);
pd(x+1,y);
pd(x,y-1);
pd(x,y+1);
until(open>=closed)or(xx[xe,ye]>0);
end;
begin
readln(ok);
for ook:=1 to ok do
begin
init;
bfs;
ans:=1;dfs1(xs,ys);
write(ans,' ');
ans:=1;dfs2(xs,ys);
writeln(ans,' ',xx[xe,ye]);
end;
end.
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator