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