最少转弯问题

《最少转弯问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、最少转弯问题（文件名TURN.PAS）给出一张地图，这张地图被分为n×m（n,m<=100）个方块，任何一个方块不是平地就是高山。平地可以通过，高山则不能。现在你处在地图的（x1,y1）这块平地，问：你至少需要拐几个弯才能到达目的地（x2,y2）？你只能沿着水平和垂直方向的平地上行进，拐弯次数就等于行进方向的改变（从水平到垂直或从垂直到水平）的次数。例如：如图1，最少的拐弯次数为5。(x1,y1)(x2,y2)（图1）输入：共三行第一行：nm第2至n+1行：整个地图地形描述（0：空地；1：高山），如（图1）第2行地形描述为：100001

2、0第3行地形描述为：0010100……最后放在同一行。第n+2行：x1y1x2y2（分别为起点、终点坐标）输出：s（即最少的拐弯次数）输入输出样例（见图1）：TURN.INTURN.OUT571000010001010000001010110000000011013175样例程序-1：PROGRAMLOKyrandia;constfi='Turn.in';fo='Turn.out';Way:array[0..6,1..2]ofshortint=((1,0),(0,1),(-1,0),(0,-1),(1,0),(0,1),(-1,0));ex

3、:array[1..3]ofshortint=(0,3,1);varM,N:byte;mem:array[0..101,0..101]ofbyte;mem2:array[1..100,1..100,0..3]ofbyte;X1,Y1,X2,Y2:byte;ans:byte;PROCEDUREInit;varf:text;i,j:byte;beginfillchar(mem,sizeof(mem),1);fillchar(mem2,sizeof(mem),255);assign(f,fi);reset(f);readln(f,N,M);for

4、j:=1toNdofori:=1toMdoread(f,mem[i,j]);read(f,Y1,X1,Y2,X2);close(f);ans:=255;end;PROCEDUREKernel(X,Y:byte;head:byte;Turn:byte);vari,j:shortint;beginif(X=X2)and(Y=Y2)thenbeginifTurn

5、2)mod4]:=Turn;mem2[X,Y,(head+3)mod4]:=Turn+1;forj:=1to3dobegini:=head+ex[j];ifmem[X+way[i,1],Y+way[i,2]]=0thenif(mem2[X,Y,imod4]

6、xt;beginassign(f,fo);rewrite(f);ifans<255thenwriteln(f,ans)elsewriteln(f,'NO');close(f);end;beginInit;Kernel(X1,Y1,0,0);Kernel(X1,Y1,1,0);Kernel(X1,Y1,2,0);Kernel(X1,Y1,3,0);Print;end.样例程序-2：programturn;constfn1='turn.in';fn2='turn.out';varn,m:integer;{n,m为地图尺寸}x1,y1,x2,y2

7、:integer;{(x1,y1)为初始块，x2,y2为目标块)}a:array[1..100,1..100]of0..1;b:array[1..100,1..100]ofinteger;{b数组为最少步数；当b[i,j]=∞时，表示不能从(x1,y1)走道(i,j);否则表示从(x1,y1)走道(i,j)的最少拐弯次数。}c:array[1..1000,1..2]ofbyte;{open,close表}procedureinit;{读入数据}varf:text;i,j:integer;beginassign(f,fn1);reset(f)

8、;readln(f,n,m);fori:=1tondoforj:=1tomdoread(f,a[i,j]);readln(f,x1,y1,x2,y2);close(f);end;