经典回溯问题- 迷宫
我们大家在小时候可能都玩过 “找路线”、“逃出迷宫” 这样的小游戏。通常的玩法一般是一开始顺着入口往后面走，遇到岔路口，就选择其中一条路往后走，走到此路无路可走的时候 ，就再退回到岔路口，然后再去选另外的一条路走，每次走到此条路不通时就返回到上一个岔路口另选一条路走 ……经历这般 “摸爬滚打”之后，最后才可能走到出口。这里编程解决迷宫的思路同样如此。
首先，还是先来做准备工作，定义一个全局的二维数组表示迷宫、一个结构体变量表示坐标，如下
<1>先来解决简单的这种迷宫（没有回路），如下：
用递归的思路，容易想到 :从入口点开始，在与它相邻各个方向中找出一可通的位置，然后跳至该处并把此位置的值置为2，然后重复以上操作，划分子问题，当最后到达规定的出口时停止算法。
代码如下：
#pragma once #include <string.h> #define N 7 int maze[N][N]={ {0,0,0,0,0,0,0}, {0,1,1,1,1,0,0}, {0,1,0,0,0,0,0}, {0,1,0,0,0,0,0}, {0,1,1,1,1,0,0}, {0,1,0,0,1,1,1}, {0,1,0,0,0,0,0}, }; typedef struct Pos { int _col; int _row; }Pos; void PrintMaze(int arr[][N]) { assert(arr); for(size_t i = 0; i< N; ++i) { for(size_t j = 0; j < N; ++j) printf("%2d ", maze[i][j]); printf("\n"); } printf("\n"); } int IsAccess(Pos cur, Pos next) { if(maze[next._row][next._col] == 1 && 0<= next._row && next._row < N && 0<= next._col && next._col < N) { return 1; } return 0; } void GetPath(Pos cur) { Pos next = cur; if(cur._col == N -1) //找到出口 { printf("出口:<%d, %d>\n", cur._row, cur._col); //return ; } maze[cur._row][cur._col] = 2; //右 next = cur; next._col+= 1; if(IsAccess(cur, next)) GetPath(next); //向上走 next = cur; next._row-= 1; if(IsAccess(cur, next)) GetPath(next); //向下 next = cur; next._row+= 1; if(IsAccess(cur, next)) GetPath(next); //左 next = cur; next._col-= 1; if(IsAccess(cur, next)) GetPath(next); }
上面代码可以找出可通的路线，但是针对带回路的路线就会出现问题，同时 此种方式不能找出最短的那条路线，并不理想。
继续往下优化 ~_~ …
<2>带环的多条线路迷宫，选择路径最短的一条线路
有一种比较巧妙的办法：改变记录迷宫线路的方式来实现。
思路：改变记录走过位置的标记方式。当前坐标位置的标记值是上一个位置的标记值加1
得到；（假如某个位置走过了，被标记为了4，那么走过的下一个位置就将其标记为5… ）
与此同时，这样的记录方式还有一好处就是间接的表示了一条路径的长度。
由于改变了标记的方式，判断下个位置是否可通的条件做相应改变
判断可通条件：当前坐标的标记值 < 下一个坐标处的标记值 或者 下一个坐标标记值为 1
注意: 由于标记为 1的坐标也表示可通，所以初始时入口处坐标不妨从2开始标记。
代码如下：
#include "Stack.h" //上次实现的栈头文件 int IsAccessInShortPath(Pos cur, Pos next) { if(( maze[cur._row][cur._col] < maze[next._row][next._col] //当前坐标的标记值 < 下一个坐标处的标记值 || maze[next._row][next._col] == 1) && 0<= next._row && next._row < N && 0<= next._col && next._col < N ) { return 1; } return 0; } Stack shortPath; //用一个全局的栈保存最短路径 void GetShortPath(Pos cur, Stack* pPath) { Pos next = cur; if(StackEmpty(pPath) == 0) //初始入口位置 记为2 maze[cur._row][cur._col] = 2; else { Pos prev = StackTop(pPath); //当前位置标记值 为上一个位置标记值+1 maze[cur._row][cur._col] = maze[prev._row][prev._col] + 1; } StackPush(pPath, cur); if(cur._col == N -1) //找到出口 { printf("出口:<%d, %d>\n", cur._row, cur._col); //每找到一条路线就和shortPath里的路线比较长短 //找到的路线更短，刷新shortPath if(StackSize(pPath) < StackSize(&shortPath) || StackEmpty(&shortPath) == 0) //初始shortPath为空，需要刷新。 { //不能直接shortPath._array = pPath->_array这样赋值 //shortPath._array = pPath->_array; //shortPath._end = pPath->_top; //shortPath._top = pPath->_top; if(shortPath._array) //刷新shortPath，由于每次额外开辟空间来保存较短路径 free(shortPath._array); //需要释放上一次开辟空间 shortPath._array = (DataType*)malloc(sizeof(DataType)* pPath->_top); memcpy(shortPath._array, pPath->_array, sizeof(DataType) * pPath->_top); shortPath._end = pPath->_top; shortPath._top = pPath->_top; } } //向上走 next = cur; next._row-= 1; if(IsAccessInShortPath(cur, next)) GetShortPath(next, pPath); //向下 next = cur; next._row+= 1; if(IsAccessInShortPath(cur, next)) GetShortPath(next, pPath); //左 next = cur; next._col-= 1; if(IsAccessInShortPath(cur, next)) GetShortPath(next, pPath); //右 next = cur; next._col+= 1; if(IsAccessInShortPath(cur, next)) GetShortPath(next, pPath); //四个方向都走不通 开始回朔，pop掉path栈里保存的路径坐标 StackPop(pPath);
}
递归的过程可参考下图：
最后再简单测一下：
void TestMaze() { Pos entry; entry._col = 1; entry._row = 6; /*GetPath(entry); PrintMaze(maze);*/ Stack path; StackInit(&path); StackInit(&shortPath); GetShortPath(entry, &path); PrintMaze(maze); while(StackEmpty(&shortPath) != 0) { Pos cur = StackTop(&shortPath); printf("(%d,%d)<-", cur._row, cur._col); StackPop(&shortPath); } printf("入口\n"); }
结果：
小结一下：
1.刷新shortPath里保存的路径，需要将path栈里存的路径整体拷贝过来，若将实现path栈底层的_array直接赋值给shortPath._array
以本迷宫为例，它会先找到 ‘厂’ 型的路线，于是shortPath._array被赋值为path->_array 保存了路径，而找第二条路径时在递归到<4, 5>处会停止，算法结束，于是导致
shortPath._array存放的路径不完整; 而整体拷贝的话，由于没到规定出口出，shortPath._array并未刷新，还保存的是上一条路径 保证正确性。
2.实现该迷宫时，默认设置出口为col = 6的位置，其实应该将出口的信息作为参数传入找路径的函数中，大家可以自行再优化。