第5讲：队列.pptVIP

5、判重： for i=1 to tail do if a[1].str = tem 最简单、最直接的判重方法。 缺点：效率低，时间慢。 head:=0; tail:=1; q[1].str:=s1; q[1].depth:=0; while headtail do begin inc(head); s:=q[head].str; step:=q[head].depth+1; sp:=pos(0,s); for i:=1 to 9 do begin tem:=s; if (i+2=sp)or(i-2=sp) then begin tem[sp]:=s[i]; tem[sp+1]:=s[i+1]; tem[i]:=0; tem[i+1]:=0; if tem=st then print(step); if not find(tem) then begin inc(tail); q[tail].str:=tem; q[tail].depth:=step; end; end; end; end; function find(tem:string):boolean; var j:integer; begin for j:=1 to tail do if tem=q[j].str then exit(true); exit(false); end; 5、最少转弯次数 给出一张地图，这张地图被分成n*m个方块任何一个方块不是高山就是平地。平地可以通过，而高山不安可以通过，现在，你处在地图的A（x1，y1）这块平地上，问：你至少需要拐几个弯才能到达目的地B（x2，y2）。 如上图中（黑色是高山），（x1，y1）到（x2，y2）至少转5个弯。 输入： 第一行：n，m（=100） 第二行：x1，y1，x2，y2（=100） 以下n行m列的矩阵，0代表高山，1代表平地。中间空格隔开。 输出： 最少拐弯次数。 样例： 输入： 5 7 1 3 1 7 0 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 0 0 1 输出： 5 分析： 关键点： 1)、从某一位置出发，在一个方向上到达的点不再需要拐弯。沿某个方向能走就走，直到遇到高山为止。 所以： 2）、从起始点（x1，y1）出发能到达他的4个方向上的所有点。不需要拐弯。这些点 的拐弯数都是0。 3）、走过的地方做标记，不能与平地和高山用一个标记？遇到已经走过的格子，只要前面不是高山可以继续往前走。 type node=record x,y:integer; depth:integer; end; var q:array[1..maxn*maxn] of node;{队列数据库} can:array[0..maxn+1,0..maxn+1] of boolean;{b[i，j]=true：平地} turn:array[1..maxn,1..maxn] of integer; {最少转弯数:标记是否已走过：初始=maxint，走过后改为拐弯数； 不能用b替代.可以代替depth} n,m,x1,y1,x2,y2,head,tail:integer; head:=0; tail:=1; q[1].x:=x1; q[1].y:=y1; q[1].depth:=-1; while headtail do begin inc(head); x0:=q[head].x; y0:=q[head].y; step:=q[head].depth+1; for i:=1 to 4 d