记录编号 | 22820 | 评测结果 | AAAAAAAAAA | ||
---|---|---|---|---|---|
题目名称 | [USACO Jan09] 激光电话 | 最终得分 | 100 | ||
用户昵称 | 是否通过 | 通过 | |||
代码语言 | Pascal | 运行时间 | 0.017 s | ||
提交时间 | 2010-12-27 20:49:12 | 内存使用 | 0.24 MiB | ||
program lphone(input,output); var a:array[1..100,1..100]of char; i,j,l:longint; b:array[1..100,1..100]of longint; q:array[1..10000,1..2]of longint; m,n:longint; head,tail:longint; x1,x2,y1,y2:longint; procedure tr1(x,y:longint); begin if a[x,y]<>'*' then begin if (b[x,y]>b[q[head,1],q[head,2]]+1) then begin inc(tail); q[tail,1]:=x; q[tail,2]:=y; b[x,y]:=b[q[head,1],q[head,2]]+1; end; if (x=x2)and(y=y2) then begin writeln(b[x,y]-1); close(output); halt; end; if x-1>0 then tr1(x-1,y); end; end; procedure tr2(x,y:longint); begin if a[x,y]<>'*' then begin if (b[x,y]>b[q[head,1],q[head,2]]+1) then begin inc(tail); q[tail,1]:=x; q[tail,2]:=y; b[x,y]:=b[q[head,1],q[head,2]]+1; end; if (x=x2)and(y=y2) then begin writeln(b[x,y]-1); close(output); halt; end; if x+1<=n then tr2(x+1,y); end; end; procedure tr3(x,y:longint); begin if a[x,y]<>'*' then begin if (b[x,y]>b[q[head,1],q[head,2]]+1) then begin inc(tail); q[tail,1]:=x; q[tail,2]:=y; b[x,y]:=b[q[head,1],q[head,2]]+1; end; if (x=x2)and(y=y2) then begin writeln(b[x,y]-1); close(output); halt; end; if y-1>0 then tr3(x,y-1); end; end; procedure tr4(x,y:longint); begin if a[x,y]<>'*' then begin if (b[x,y]>b[q[head,1],q[head,2]]+1) then begin inc(tail); q[tail,1]:=x; q[tail,2]:=y; b[x,y]:=b[q[head,1],q[head,2]]+1; end; if (x=x2)and(y=y2) then begin writeln(b[x,y]-1); close(output); halt; end; if y+1<=m then tr4(x,y+1); end; end; begin assign(input,'lphone.in'); reset(input); readln(m,n); for i:=1 to n do begin for j:=1 to m do begin read(a[i,j]); if a[i,j]='C' then begin if l=0 then begin x1:=i; y1:=j; l:=1; end else begin x2:=i; y2:=j; end; end; end; readln; end; close(input); for i:=1 to n do for j:=1 to m do b[i,j]:=maxlongint; assign(output,'lphone.out'); rewrite(output); head:=1; tail:=1; q[head,1]:=x1; q[head,2]:=y1; b[q[head,1],q[head,2]]:=0; repeat if q[head,1]-1>0 then tr1(q[head,1]-1,q[head,2]); if q[head,1]+1<=n then tr2(q[head,1]+1,q[head,2]); if q[head,2]-1>0 then tr3(q[head,1],q[head,2]-1); if q[head,2]+1<=m then tr4(q[head,1],q[head,2]+1); inc(head); until head>tail; close(output); end.