讨论 / Bfs---一次AC
没13 2009-07-26 19:54:00
点我顶贴 收藏 删除
program bfs_jjjy;

type

rec=record

x,y:integer;

end;

var

s:array[1..1000] of ansistring;

dui:array[1..1000000] of rec;

d:array[0..1000000] of longint;

g:array[1..4,1..2] of longint;

head,tail:longint;

i,k,n,x1,x2,y1,y2,xx,yy:integer;

f:boolean;

begin

readln(n);

for i:=1 to n do

readln(s[i]);

head:=0; tail:=1;

readln(x1,y1);

readln(x2,y2);

g[1,1]:=1; g[1,2]:=0;

g[2,1]:=-1; g[2,2]:=0;

g[3,1]:=0; g[3,2]:=1;

g[4,1]:=0; g[4,2]:=-1;

dui[tail].x:=x1; dui[tail].y:=y1; s[x1][y1]:=’1’ ;

f:=false; d[1]:=1;

repeat

inc(head);

for k:=1 to 4 do begin

xx:=dui[head].x+g[k,1]; yy:=dui[head].y+g[k,2];

if (xx=x2) and (yy=y2) then begin f:=true; break end;

if (xx>0) and (xx<=n) and (yy>0) and (yy<=n) and (s[xx][yy]=’0’) then begin

s[xx][yy]:=’1’;

inc(tail); d[tail]:=d[head]+1;

dui[tail].x:=xx; dui[tail].y:=yy;

end;

end;

until f;

write(d[head]);

readln;

readln;

end.

查看更多回复
提交回复