题意：
FJ的屋子在平面坐标(0, 0)的位置，贝茜所在的牛棚则位于坐标(X,Y) (-500 <= X <= 500; -500 <= Y <= 500)处。当然咯，FJ也看到了地上的所有N(1 <= N <= 10,000)个泥塘，第i个泥塘的坐标为(A_i, B_i) (-500 <= A_i <= 500；-500 <= B_i <= 500)。每个泥塘都只占据了它所在的那个格子。不能走到池塘，而且只能平行x，y轴走。
思路：
bfs，加上记忆化
程序：
type
Point=
record
x,y,w:longint;
end;
const
maxn=
500;
dx:
array [
1..
4]
of longint=(
1,-
1,
0,
0);
dy:
array [
1..
4]
of longint=(
0,
0,
1,-
1);
var
a:
array [-maxn-
2..maxn+
1,-maxn-
2..maxn+
2]
of boolean;
x,y,x1,y1,n,i,j:longint;
state:
array [
1..
1000000]
of Point;
function cheak(x,y:longint):boolean;
begin
if a[x,y]
then exit(
false);
if (x<-
500)
or (x>
500)
or (y<-
500)
or (y>
500)
then exit(
false);
exit(
true);
end;
procedure bfs;
var
y1,x1,i,j,head,tail:longint;
begin
head:=
0; tail:=
1;
state[
1].x:=
0; state[
1].y:=
0;
state[
1].w:=
0;
repeat
inc(head);
for i:=
1 to 4 do
begin
x1:=state[head].x+dx[i];
y1:=state[head].y+dy[i];
if cheak(x1,y1)
then
begin
inc(tail);
a[x1,y1]:=
true;
state[tail].x:=x1;
state[tail].y:=y1;
state[tail].w:=state[head].w+
1;
end;
if (x1=x)
and (y1=y)
then
begin
writeln(state[tail].w);
halt;
end;
end;
until head=tail;
end;
begin
readln(x,y,n);
for i:=
1 to n
do
begin
readln(x1,y1);
a[x1,y1]:=
true;
end;
bfs;
writeln(-
1);
end.
转载请注明原文地址: https://ju.6miu.com/read-600278.html
