给一个地图，其中有障碍物，开始人在起点的面对方向任意，求从起点到终点最少转几次弯。
f[pos,x,y]表示人在(x,y)位置，面向方向pos时的最小步数，用BFS或SPFA即可。
View Code 1 program lphone(input,output); 2 type 3 node = record 4 xx,yy,pos : integer; 5 end; 6 var 7 d : array[1..4,0..101,0..101] of longint; 8 v : array[1..4,0..101,0..101] of boolean; 9 q : array[0..400000] of node; 10 a : array[0..101,0..101] of char; 11 x : array[1..4] of longint=(-1,0,1,0); 12 y : array[1..4] of longint=(0,1,0,-1); 13 start,goal : node; 14 n,m : longint; 15 procedure init; 16 var 17 i,j : longint; 18 begin 19 readln(m,n); 20 for i:=1 to n do 21 begin 22 for j:=1 to m do 23 begin 24 read(a[i,j]); 25 if a[i,j]='C' then 26 if goal.xx=0 then 27 begin 28 goal.xx:=i; 29 goal.yy:=j; 30 end 31 else 32 begin 33 start.xx:=i; 34 start.yy:=j; 35 end; 36 end; 37 readln; 38 end; 39 end; { init } 40 procedure spfa; 41 var 42 head,tail : longint; 43 i : longint; 44 newx,newy,newpos : longint; 45 begin 46 fillchar(d,sizeof(d),63); 47 fillchar(v,sizeof(v),false); 48 head:=0; 49 tail:=4; 50 for i:=1 to 4 do 51 begin 52 q[i].xx:=start.xx; 53 q[i].yy:=start.yy; 54 q[i].pos:=i; 55 v[q[i].pos,q[i].xx,q[i].yy]:=true; 56 d[q[i].pos,q[i].xx,q[i].yy]:=0; 57 end; 58 while head 0)and(newx<=n)and(newy>0)and(newy<=m) then 65 if a[newx,newy]<>'*' then 66 if d[q[head].pos,q[head].xx,q[head].yy] >1; 115 for i:=1 to 4 do 116 if d[i,goal.xx,goal.yy]