(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)
【算法分析】
用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪些点走过了。每个点用两个数字来描述，一个表示行号，另一个表示列号。对于某一个点(x，y)，四个可能走的方向的点描述如下表：
4 1 x,y 3 2 对应的位置为：(x-1, y)，(x, y+1)，(x+1, y)，(x, y-1)。所以每个点都要试探四个方向，如果没有走过(数组b相应的点的值为0)且可以走(数组a相应点的值为1)同时不越界，就走过去，再看有没有到达终点，到了终点则输出所走的路，否则继续走下去。 这个查找过程用search来描述如下：
procedure search(x, y, b, p)；{x，y表示某一个点，b是已经过的点的情况，p是已走过的路} begin
for i:＝1 to 4 do{分别对4个点进行试探} begin
先记住当前点的位置，已走过的情况和走过的路； 如果第i个点(xl，y1)可以走，则走过去；
如果已达终点，则输出所走的路径并置有路可走的信息， 否则继续从新的点往下查找search(xl，y1，b1，p1)； end； end；
【思考与提高】 该程序通过引进新的变量和数组来继续新的查找，如果不引进新的变量和数组，那么每一次返回时要将原来的值还原才行，如果那样，程序应如何修改?其实那样更加符合回溯的思想——换条路再试。这类问题也可以归为搜索的问题，如果m和n的值相对比较大，则解可能很多，若题目只要找到一条路就结束程序时，在程序的输出部分后面加上一个halt就行了。
有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层的结点，看起来如同树枝一样，对于其中的“枯枝”——明显无用的节点可以先行“剪掉”，从而提高搜索速度。
1.6 单向双轨道
源程序名 track.???（pas, c, cpp） 可执行文件名 track.exe 输入文件名 track.in 输出文件名 track.out 【问题描述】
如图所示l，某火车站有B，C两个调度站，左边入口A处有n辆火车等待进站(从左到右以a、b、c、d编号)，右边是出口D，规定在这一段，火车从A进入经过B、C只能从左向右单向开，并且B、C调度站不限定所能停放的车辆数。 出口 入口
D A B C
从文件输入n及n个小写字母的一个排列，该排列表示火车在出口D处形成的从左到右的火车编号序列。输出为一系列操作过程，每一行形如“h L R”的字母序列，其中h为火车编号，L为h车原先所在位置(位置都以A、B、C、D表示)，R为新位置。或者输出‘NO’表示不能完成这样的调度。 【输入】 一个数n(1 这是一道类似于栈的操作题目，只不过是有两个栈B和C可以操作，而对于A序列里的元素，既可以进入B，也可以进入C，或直接到D。解决问题可以从D序列出发反过来看，当前要到D的字符在哪里，如果在A，再看它前面有没有字符，如果有，先让它们进栈(B或C)，否则直接到D；如果在B，看是否是栈顶元素，如果是，直接到D，否则将上面的字符进C；如果在C，看是否是栈顶元素，如果是，直接到D，否则无法进行操作，因为只能向右不能向左，这时要回溯。如果所有的情况都检测过，某个字符不能进行到D的操作，则输出无解信息。 由于A里的非直接进入D的字符可以进入B或C，可以跟二进制建立起对应关系，将所有情况列举一遍，再找出其中步骤最少的输出。 1.7 组合的输出 源程序名 track.???（pas, c, cpp） 可执行文件名 track.exe 输入文件名 track.in 输出文件名 track.out 【问题描述】 排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r<＝n)，我们可以简单地将n个元素理解为自然数1，2，?，n，从中任取r个数。 现要求你不用递归的方法输出所有组合。 例如n＝5，r＝3，所有组合为： l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 【输入】 一行两个自然数n、r(1 所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。 【样例】 compages.in compages.out 5 3 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5 【算法分析】 如果通过循环加递归来实现回溯比较简单，相应程序为： const max=20; var a:array[0..max]of integer; n,r:1..max; procedure compages(k:integer);{选取第k个元素} var i,j:integer; begin {当前所选元素最小为前一个元素加1，最大为n-(r-k)，因为后面还有(r-k)个元素要选取，至少为每次选取留一个} for i:=a[k-1]+1 to n-(r-k) do begin a[k]:=i; {选取一个元素} if k=r then begin for j:=1 to r do write(a[j]:3); writeln; end else compages(k+1); end; end; begin {main} readln(n,r); compages(1); {从第一个元素开始选取给合数} end. 本题要求不用递归来实现回溯，关键要定好回溯的条件。如果选取第i个元素时选择了a[i]，根据输出条件应有a[i]-i<＝n-r，如果不满足这个条件说明当前第i个元素已再无数可取，要进行回溯，将其值减1，退到上一步将上一步原来的值再增加1，重复上述过程。当全部选取完时，i回到了0，a[0]的值增加1后变为1，这是整个选取过程结束的条件。 1.8 售货员的难题 源程序名 salesman.???（pas, c, cpp） 可执行文件名 salesman.exe 输入文件名 salesman.in 输出文件名 salesman.out 【问题描述】 某乡有n个村庄(1 题目给定的村庄数不多(≤40)，所以可以用回溯的方法，从起点(第一个村庄)出发找出所有经过其他所有村庄的回路，计算其中的最短路程。当村庄数n比较大时这种方法就不太适用了。 用一个过程road(step，line：byte)来描述走的状况，其中step是当前已到村庄数、line是当前所在的村庄。如果step＝n，下面只能回起点了，直接看第line个村庄到第一个村庄的路程加上已走的总路程，如果比最小值还小则替换最小值(要保存路径的话也可保存，这是回溯算法的优点，考虑到达最小值的路径可能不止一条，不便于测试，题目没要求输出路径)。如果step还小于n，那么将还没有到过的村庄一个一个地试过去，再调用下一步road(step+1，新到的村庄号)。