最少转弯问题.doc

一、最 少 转 弯 问 题（文件名TURN.PAS）给出一张地图，这张地图被分为nm（n,m=100）个方块，任何一个方块不是平地就是高山。平地可以通过，高山则不能。现在你处在地图的（x1,y1）这块平地，问：你至少需要拐几个弯才能到达目的地（x2,y2）？你只能沿着水平和垂直方向的平地上行进，拐弯次数就等于行进方向的改变（从水平到垂直或从垂直到水平）的次数。例如：如图1，最少的拐弯次数为5。 ( x1,y1)(x2,y2)（图1） 输入：共三行第一行：n m第2至n+1行：整个地图地形描述（0：空地；1：高山），如（图1）第2行地形描述为：1 0 0 0 0 1 0 第3行地形描述为：0 0 1 0 1 0 0 最后放在同一行。 第n+2行：x1 y1 x2 y2 （分别为起点、终点坐标）输出：s （即最少的拐弯次数）输入输出样例（见图1）：TURN.INTURN.OUT5 71 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 01 3 1 75样例程序-1：PROGRAM LOKyrandia;const fi=Turn.in; fo=Turn.out; Way:array0.6,1.2of shortint=(1,0),(0,1),(-1,0),(0,-1),(1,0),(0,1),(-1,0); ex:array1.3of shortint=(0,3,1);var M,N:byte; mem:array0.101,0.101of byte; mem2:array1.100,1.100,0.3of byte; X1,Y1,X2,Y2:byte; ans:byte; PROCEDURE Init; var f:text; i,j:byte; begin fillchar(mem,sizeof(mem),1); fillchar(mem2,sizeof(mem),255); assign(f,fi); reset(f); readln(f,N,M); for j:=1 to N do for i:=1 to M do read(f,memi,j); read(f,Y1,X1,Y2,X2); close(f); ans:=255; end; PROCEDURE Kernel(X,Y:byte;head:byte;Turn:byte); var i,j:shortint; begin if (X=X2)and(Y=Y2) then begin if Turnans then ans:=Turn; exit; end; mem2X,Y,head:=Turn; mem2X,Y,(head+1)mod 4:=Turn+1; mem2X,Y,(head+2)mod 4:=Turn; mem2X,Y,(head+3)mod 4:=Turn+1; for j:=1 to 3 do begin i:=head+exj; if memX+wayi,1,Y+wayi,2=0 then if (mem2X,Y,i mod 4ans) and (mem2X,Y,i mod 4mem2X+wayi,1,Y+wayi,2,i mod 4) then Kernel(X+wayi,1,Y+wayi,2,i mod 4,mem2X,Y,i mod 4); end; end; PROCEDURE Print; var f:text; begin assign(f,fo); rewrite(f); if ans255 then writeln(f,ans) else writeln(f,NO); close(f); end;begin Init; Kernel(X1,Y1,0,0); Kernel(X1,Y1,1,0); Kernel(X1,Y1,2,0); Kernel(X1,Y1,3,0); Print;end.样例程序-2：program turn;const fn1=turn.in; fn2=turn.out;var n,m:integer; n,m为地图尺寸 x1,y1,x2,y2:integer; (x1,y1)为初始块，x2,y2为目标块) a:array1.100,1.100 of 0.1; b:array1.100,1.100 of integer; b数组为最少步数；当bi,j=时，表示不能从(x1,y1)走道(i,j);否则表示从(x1,y1)走道(i,j)的最少拐弯次数。 c:array1.1000,1.2 of byte; open,close表procedure init; 读入数据var f:text; i,j:integer;begin assign(f,fn1); reset(f); readln(f,n,m); for i:=1 to n do for j:=1 to m do read(f,ai,j); readln(f,x1,y1,x2,y2); close(f);end;procedure calc;var i,j,k,x,y:integer; open,closed:integer; procedure evaluate(i,j,l:integer); 赋值 begin k:=k+l; if bi,j=1) do evaluate(k,y,-1); 向下扩展，直到有高山相阻 k:=x+1; while(ak,y=0) and (k=1) do evaluate(x,k,-1); 向左扩展，直到有高山相阻 k:=y+1; while(ax,k=0) and (K=closed) or (bx2,y2maxint)end;procedure print;var f:text;begin assi