Question

free pascal的一道题

【问题描述】
给出一张地图，这张地图被分为 n×m（n,m<=100）个方块，任何一个方块不是平地就是高山。平地可以通过，高山则不能。现在你处在地图的（x1,y1）这块平地，问：你至少需要拐几个弯才能到达目的地（x2,y2）？你只能沿着水平和垂直方向的平地上行进，拐弯次数就等于行进方向的改变（从水平到垂直或从垂直到水平）的次数。例如：如图 1，最少的拐弯次数为5。

【输入格式】
第 1行：n m
第 2至n+1行：整个地图地形描述（0：空地；1：高山），
如图,第2行地形描述为：1 0 0 0 0 1 0
第3行地形描述为：0 0 1 0 1 0 0
……
第n+2行：x1 y1 x2 y2 （分别为起点、终点坐标）
【输出格式】
s （即最少的拐弯次数）
【输入样例】
5 7
1 0 0 0 0 1 0
0 0 1 0 1 0 0
0 0 0 0 1 0 1
0 1 1 0 0 0 0
0 0 0 0 1 1 0
1 3 1 7
【输出样例】
5

Answer 1

program p1468;
var
a,c:array[1..100,1..100] of longint;
b:array[1..100,1..20] of longint;
x1,x2,y1,y2,i,j,k,head,tail,m,n,x,y:longint;
Procedure sou(ii,jj,kk:longint);
begin
k:=k+kk;
if c[ii,jj]<10000 then exit;
tail:=tail+1;
b[tail,1]:=ii;
b[tail,2]:=jj;
c[ii,jj]:=c[x,y]+1;
end;
Begin
readln(n,m);
for i:=1 to n do
for j:=1 to m do
begin
read(a[i,j]);
c[i,j]:=10000;
end;
readln(x1,y1,x2,y2);
head:=0; tail:=1;
b[1,1]:=x1; b[1,2]:=y1;
c[x1,y1]:=-1;
repeat
head:=head+1;
x:=b[head,1]; y:=b[head,2];
k:=x-1;
while (k>=1) and (a[k,y]=0) do sou(k,y,-1);
k:=x+1;
while (k<=n) and (a[k,y]=0) do sou(k,y,1);
k:=y-1;
while (k>=1)and(a[x,k]=0) do sou(x,k,-1);
k:=y+1;
while (k<=m)and(a[x,k]=0) do sou(x,k,1);
until (head>=tail) or (c[x2,y2]<10000);
writeln(c[x2,y2]);
end.

Answer 2

直接用宽搜来解决。