算法试题之二.docVIP

4.求迷宫的路径。 回溯算法的公式如下: 一，用一个二维数组表示出迷宫问题 1 2 3 4 5 6 7 8 9 10 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 1 1 0 x,y 0 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 二，探索路径 坐标1： （x+1, y+0） 坐标2： （x+0, y+1） 坐标3： （x-1, y+0） 坐标4： （x+0, y-1） 采取新数组（U，V）表示跳的坐标值： U:=X+a[j] j= 1,2,3…,8 V:=Y+b[j] 此程序描述参考跳马。 例题： [记录走迷宫的路径问题描述]： 有一个m*n格的迷宫（m：表示行，n：表示列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据的起始点，结束点（起始点和结束点都是用两个数据来描述，分别表示这个点的行号和列号）。现在要求你编程找出所有可行的通道，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应的信息（用-1表示走投无路）。 [输入]： 第一行是两个数m，n（1m, n15）,接下来是m行n列有1和0组成的数据，最后两行是起始点和结束点。 [输出]： 所有可行的路径，描述一个点时可用（x,y）的形式，除开始点外，其他的都要用‘-’表示方向。 如果没有一条可行的路径，则使程序输出-1。 [样例] maze.in 5 6 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 5 6 maze.out ‘(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(2,5)-(3,5)-(3,4)-(3,3)-(4,3)-(4,4)-(4,5)-(5,5)-(5,6)’ 分析： 用一个数组a来存放迷宫可走的情况，用另一个数组b来存放哪些点已经走过了。对于中间某一个点（x,y）,则它有可能有四个可走的方向，对应位置表示为：（x-1,y）,（x,y+1）,（x+1,y）,（x,y-1）。每个点都会有四个方向可走。如果没有走过（数组b相应点对应的值为0）且可以走（数组a相应点的值为1）同时不越界，那么就走过去，判断一下有没有到达终点。如果到了终点，输出所走的路径，否则继续走下去。 探索过程我们写成一个过程try search procedure try(x,y,b,p ); {x,y表示某一个点，b表示已经走过点的情况，p是已走过的路径} begin for i:=1 to 4 do {分别对4个点进行探索} begin 1.(x,y)先记住当前点的位置，还要记住走过的情况和走过的路； 2.如果第i个点可以走（u,v），则走过去； 3.判断如果到终点，则输出所走的路径，且置有路可走的信息。 4.否则继续从新的点往下查找try(x,y,b,p); End; End; 参考程序： var a,b:array[1..15,1..15] of 0..1; p:string; procedure try(x,y:integer;b:arr;p:string); var i,j,k,x1,y1:integer; b1:arr; p1:string; begin for i:= to 4 do begin for j:=1 to m do for k:=1 to n do b1[j,k]:=b[j,k]; p1:=p; x1:=x; y1:=y; {} case i of 1: if (y1) and (a[x,y-1]=1) and (b[x,y-1]=0) then y1:=y-1; 2: if (x1) and (a[x-1,y]=1) and (b[x-1,y]=0) then x1:=x-1; 3: if (yn) and (a[x,y+1]=1) and (b[x,y+1]=0) then y1:=y+1; 4: if (xm) and (a[x+1,y]=1) and (b[x+1,y]=0) then x1:=x+1; end; if (x1x)