最少轉(zhuǎn)彎問題

1、一、最少轉(zhuǎn)彎問題（文件名 TURN.PAS）給出一張地圖，這張地圖被分為nXm （n,m=100）個方塊，任何一個方塊不是平地就 是高山。平地可以通過，高山則不能?，F(xiàn)在你處在地圖的（x1,y1 ）這塊平地，問：你至少 需要拐幾個彎才能到達(dá)目的地（x2,y2） ?你只能沿著水平和垂直方向的平地上行進(jìn)，拐彎 次數(shù)就等于行進(jìn)方向的改變（從水平到垂直或從垂直到水平）的次數(shù)。例如：如圖1，最少的拐彎次數(shù)為5。輸入：共三行第一行：n m第2至n+1行：整個地圖地形描述（0：空地；1：高山）， 如（圖1）第2行地形描述為：1 0 0 0 0 1 0第3行地形描述為：0 0 1 0 1 0 0最后放在同一行。

2、第n+2行：x1 y1 x2 y2（分別為起點(diǎn)、終點(diǎn)坐標(biāo)）輸出：s （即最少的拐彎次數(shù)）輸入輸出樣例（見圖1）：TURN.INTURN.OUT5 751 0 0 0 0 1 00 0 1 0 1 0 00 0 0 0 1 0 10 1 1 0 0 0 00 0 0 0 1 1 01 3 1 7樣例程序-1：PROGRAM LOKyrandia;constr* 5 m,ii-lurn.in;fo=Turn.out;Way:array0.6,1.2ofshortint=(1,0),(0,1),(-1,0),(0,T),(1,0),(0,1),(T,0);ex:array1.3of shortint

3、=(0,3,1);varM,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;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 j:=1 to N dofor i:=1 to M doread(f,memi,j);read(f,Y1,X

4、1,Y2,X2);close(f);ans:=255;end;PROCEDURE Kernel(X,Y:byte;head:byte;Turn:byte);vari,j:shortint;beginif (X=X2)and(Y=Y2) thenbeginif Turnans thenans:=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 dobegini:=head+ex

5、j;if memX+wayi,1,Y+wayi,2=0 thenif (mem2X,Y,i mod 4ans) and (mem2X,Y,i mod 4mem2X+wayi,1,Y+wayi,2,i mod 4) thenKernel(X+wayi,1,Y+wayi,2,i mod 4,mem2X,Y,i mod 4);end;end;PROCEDURE Print;varf:text;beginassign(f,fo);rewrite(f);if ans255 thenwriteln(f,ans)elsewriteln(f,NO);close(f);end;beginInit;Kernel(

6、X1,Y1,0,0);Kernel(X1,Y1,1,0);Kernel(X1,Y1,2,0);Kernel(X1,Y1,3,0);Print;end.樣例程序-2： program turn; constfn1=turn.in;fn2=turn.out;varn,m:integer;n,m 為地圖尺寸x1,y1,x2,y2:integer; (x1,y1)為初始塊，x2,y2 為目標(biāo)塊)a:array1.100,1.100 of 0.1;b:array1.100,1.100 of integer; b 數(shù)組為最少步數(shù)；當(dāng) bi,j=8時，表示不能 從(x1,y1)走道(i,j);否則表示從(x

7、1,y1)走道(i,j)的最少拐彎次數(shù)。c:array1.1000,1.2 of byte;open,close 表procedure init;讀入數(shù)據(jù)varf:text;i,j:integer;beginassign(f,fn1);reset(f);readln(f,n,m);for i:=1 to n dofor j:=1 to m doread(f,ai,j);readln(f,x1,y1,x2,y2);close(f);end;procedure calc;vari,j,k,x,y:integer;open,closed:integer;procedure evaluate(i,j,l:integer);賦值begink:=k+l;if bi,j=1) do evaluate(k,y,-1); 向下擴(kuò)展，直到有高山相阻 k:=x+1;while(ak,y=0) and (k=1) do evaluate(x,k,-1); 向左擴(kuò)展，直到有高山相阻 k:=y+1;while(ax,k=0) and (K=closed) or (bx2,y2maxint) end;procedure print;varf:text;begina