广度(宽度)优先搜索l教材课程.ppt

【深搜参考程序】 program EX8_4_1; const maxn=50; var map:array [1..maxn,1..maxn] of integer; f:boolean; n,m,i,j,desx,desy,soux,souy,totstep:integer; route:array[1..maxn] of record x,y : integer; end; procedure move(x,y,step:integer); begin map[x,y]:=step; //走一步，作标记，把步数记下来 route[step].x := x; route[step].y:= y; //记路径 if (x=desx) and (y=desy) then begin f:=true; totstep:=step; end else begin if (ym) and (map[x,y+1]=0) then move (x,y+1,step+1); //向右 if not f and (xn)and(map[x+1,y]=0) then move(x+1,y ,step+1); //往下 if not f and (y1)and(map[x,y-1]=0) then move(x,y-1, step+1); //往左 if not f and (x1)and(map[x-1,y]=0) then move(x-1,y, step+1); //往上 end; end; BEGIN readln(n,m); //n行m列的迷宫 for i:=1 to n do //读入迷宫，0表示通，-1表示不通 begin for j:=1 to m do read(map[i,j]); readln; end; write(input the enter:); readln(soux,souy); //入口 write(input the exit:); readln(desx,desy); //出口 f:=false; //f=false表示无解；f=true表示找到了一个解 move(soux,souy,1); if f then for i:=1 to totstep do //输出直迷宫的路径 write(route[i]:4); else writeln (no way.); END. 【广搜参考程序】 program EX8_4_2; const maxn=50; u:array[1..4] of integer=(0,1,0,-1); w:array[1..4] of integer=(1,0,-1,0); var map:array [1..maxn,1..maxn] of integer; f:boolean; n,m,i,j,desx,desy,soux,souy,head,tail,x,y:integer; route:array[1..maxn] of record x,y,pre : integer; end; procedure print(d:integer); begin if route[d].pre0 then print(route[d].pre); write((,route[d].x,,,route[d].y,)); end; BEGIN readln(