Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

帮我看看,,,TLE!!--pascal

Posted by wy54224 at 2011-04-09 16:44:21 on Problem 3083 and last updated at 2011-04-16 19:40:16
const 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator