?? ex.dpr
字號(hào):
{
BFS
}
program Ural_1325(Input,Output);
const
Direction:array[1..8]of record
x,y:ShortInt;
end=((x:1;y:1),(x:1;y:-1),(x:-1;y:1),(x:-1;y:-1),(x:1;y:0),(x:0;y:1),(x:-1;y:0),(x:0;y:-1));
MaxSize=500;
type
TIndex=Longint;
TQueue=array[1..MaxSize*MaxSize]of record
x,y:TIndex;
end;
TStep=array[1..MaxSize,1..MaxSize]of TIndex;
TMap=array[1..MaxSize,1..MaxSize]of Char;
var
M,N:TIndex;
Sx,Sy:TIndex;
Tx,Ty:TIndex;
Map:TMap;
Pop,Push:TIndex;
PopT,PushT:TIndex;
Queue,QueueT:TQueue;
Dist,Times:TStep;
procedure BFS_FloodFill(x,y:TIndex);
var
d:TIndex;
tx,ty:TIndex;
begin
PopT:=1;
PushT:=2;
QueueT[1].x:=x;
QueueT[1].y:=y;
while PopT<PushT do
begin
with QueueT[PopT] do
for d:=1 to 8 do
begin
tx:=x+Direction[d].x;
ty:=y+Direction[d].y;
if (tx<1) or (tx>M) or (ty<1) or (ty>N) then Continue;
if (Map[tx,ty]='0') or (Times[tx,ty]>0) then Continue;
if Map[x,y]=Map[tx,ty] then
begin
Times[tx,ty]:=Times[x,y];
QueueT[PushT].x:=tx;
QueueT[PushT].y:=ty;
Inc(PushT);
end
else
begin
Times[tx,ty]:=Times[x,y]+1;
Queue[Push].x:=tx;
Queue[Push].y:=ty;
Inc(Push);
end;
end;
Inc(PopT);
end;
end;
procedure BFS_Times;
begin
FillChar(Times,SizeOf(Times),0);
Pop:=1;
Push:=2;
Queue[1].x:=Sx;
Queue[1].y:=Sy;
Times[Sx,Sy]:=1;
while Pop<Push do
begin
with Queue[Pop] do BFS_FloodFill(x,y);
Inc(Pop);
end;
end;
procedure BFS_Dist;
var
d:TIndex;
tx,ty:TIndex;
begin
FillChar(Dist,SizeOf(Dist),0);
Pop:=1;
Push:=2;
Queue[1].x:=Sx;
Queue[1].y:=Sy;
Dist[Sx,Sy]:=1;
while Pop<Push do
begin
with Queue[Pop] do
for d:=1 to 8 do
begin
tx:=x+Direction[d].x;
ty:=y+Direction[d].y;
if (tx<1) or (tx>M) or (ty<1) or (ty>N) then Continue;
if (Map[tx,ty]='0') or (Dist[tx,ty]>0) then Continue;
if (Map[x,y]=Map[tx,ty])
or ((Map[x,y]<>Map[tx,ty]) and (Times[tx,ty]=Times[x,y]+1)) then
begin
Dist[tx,ty]:=Dist[x,y]+1;
Queue[Push].x:=tx;
Queue[Push].y:=ty;
Inc(Push);
end;
end;
Inc(Pop);
end;
end;
procedure Main;
var
i,j:TIndex;
begin
Readln(M,N);
Readln(Sx,Sy);
Readln(Tx,Ty);
for i:=1 to M do
begin
for j:=1 to N do
Read(Map[i,j]);
Readln;
end;
BFS_Times;
BFS_Dist;
if Dist[Tx,Ty]=0 then
Writeln('0 0')
else
Writeln(Dist[Tx,Ty],' ',Times[Tx,Ty]-1);
end;
begin
Main;
end.
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -