4.求迷宫的路径。
回溯算法的公式如下:
一，用一个二维数组表示出迷宫问题
1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 x,y 1 1 1 0 0 0 0 1 1 0 1 1 0 1 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 1 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
- 1 -
V:=Y+b[j]
此程序描述参考跳马。 例题：
[记录走迷宫的路径问题描述]：
有一个m*n格的迷宫（m：表示行，n：表示列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据的起始点，结束点（起始点和结束点都是用两个数据来描述，分别表示这个点的行号和列号）。现在要求你编程找出所有可行的通道，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应的信息（用-1表示走投无路）。
[输入]：
第一行是两个数m，n（1 [输出]： 所有可行的路径，描述一个点时可用（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; - 2 - 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 (y>1) and (a[x,y-1]=1) and (b[x,y-1]=0) then y1:=y-1; 2: if (x>1) and (a[x-1,y]=1) and (b[x-1,y]=0) then x1:=x-1; 3: if (y if (x1<>x) or (y1<>y) then begin b1[x1,y1]:=1; p1:=p1+'->('+chr((ord('0')+x1)+','+chr((ord('0')+y1)+')'; {字符串表示出来} if (x1=ex) and (y1=ey) then {判断是否到终点 } begin writeln(p1); f:=true; end; else try(x1,y1,b1,p1); end; end; end; begin assign(input,'maze.in'); assign(output,'maze.out'); reset(input); rewrite(output); readln(m,n); for i:=1 to m do { 初始化迷宫 } for j:=1 to n do read(a[i,j]); for i:=1 to m do { 初始化走过路径} for j:=1 to n do b[i,j]:=0; readln(bx,by); readln(ex,ey); b[bx,by]:=1; f:=false; - 3 - p:='('+chr((ord'0')+bx)+','+chr((ord('0')+by)+')'; {字符串表达} {(1,5)} try(bx,by,b,p); if not f then writeln('-1'); close(input); close(output); end. 回溯算法的一般形式表示如下： procedure back(n);{ } k ---1 while 条件k>0 do begin if 还有没检验过的x(k) 且x(k)是其中可能的一个解 then if 如果存在根结点到x(k)是一条到到达答案结点的路径 then 输出x(1),x(2),….x(k)路径 If k-----k+1 Else 回溯到前一个位置 结束 有趣的四色问题 人人都熟悉地图，可是绘制一张普通的政区图，至少需要几种颜色，才能把相邻的政区或区域通过不同的颜色区分开来，就未必是一个简单的问题了。 这个地图着色问题，是一个著名的数学难题。大家不妨用一张中国政区图来试一试，无论从哪里开始着色，至少都要用上四种颜色，才能把所有省份都区别开来。所以，很早的时候就有数学家猜想：\任何地图的着色，只需四种颜色就足够了。\这就是\四色问题\这个名称的由来。 数学史上正式提出\四色问题\的时间是在1852年。当时伦敦的大学的一名学生法朗西斯向他的老师、著名数学家、伦敦大学数学教授莫根提出了这个问题，可是莫根无法解答，求助于其它数学家，也没有得到答案。于是从那时起，这个问题便成为数学界的一个\悬案\。 一直到二十年前的1976年9月，《美国数学会通告》正式宣布了一件震撼全球数学界的消息：美国伊利诺斯大学的两位教授阿贝尔和哈根，利用电子计算机证明了\四色问题\这个猜想是完全正确的！他们将普通地图的四色问题转化为2000个特殊图的四色问题，然后在电子计算机上计算了足足1200个小时，最后成功地证明了四色问题。 现在，就让我们也来当一当解决“悬案”的高手： 〖问题描述〗 设有如下图所示的地图，每个区域代表一个省，区域中的数字代表省的编号，将每个省涂上红（R），蓝（B），白（W），黄（Y）四种颜色之一，使相邻的省份有不同的颜色。 1 2 5 输入：用邻接矩阵表示地图。从文件中读入，文件格式如下： N （有N个省） N行用空格隔开的0/1串 （1表示相邻，0表示不相邻） - 4 - 3 4 6 输出：RBWY串 〖题目分析〗 这是一道非常典型的回溯题目。解法与“八皇后问题”如出一辙。在填写每一个省的颜色时检查与相邻已填省份的颜色是否相同。如果不同，则填上；如果相同（冲突），则另选一种；如果已没有颜色可供选择，则回溯到上一省份。重复这一过程，直到所有省的颜色都已填上。 最主要的问题在于如何解决相邻省的颜色冲突。对每一个省份，可供选择的颜色一共有四种；对省份I来说颜色X可填的条件是编号为1~(I-1)且与省I相邻的省份的颜色都不是X。 〖数据结构〗 1、解决方案：用数组S存储。1-4表示四种颜色，输出时再转化成字符； 2、地图：用 N X N 数组A存储。a[i,j]=0则表示省I和省J不相邻，a[i,j]=1则表示相邻。 再例： 设有如下地图，每个区域代表一个省，区域中的数字表示省的编号，现在要求给每个省涂上红r、蓝b、黄y、白w四种颜色之一，同时使相邻的省份以不同的颜色区分。 a[x,y]: 1 表示相邻即x省与y省相邻 0表示不相邻即x省与y省不相邻 1 2 3 4 5 6 7 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 第三步：从编号1的省开始填色。 第四步：如果颜色相同，则把四种颜色全部探索一遍，都不行，则上退一个省。 可以讲解的参考程序： program tt; const num=20; var a:array [1..num,1..num] of 0..1; ｛省份相邻位置矩阵｝ s:array [1..num] of 0..4; {用1-4分别代表RBWY四种颜色;0代表末填进任何颜色} k1,k2,n:integer; function pd(i,j:integer):boolean;{判断可行性：第i个省填上第J种颜色} - 5 -