经典回溯问题- 迷宫

我们大家在小时候可能都玩过 “找路线”、“逃出迷宫” 这样的小游戏。通常的玩法一般是一开始顺着入口往后面走，遇到岔路口，就选择其中一条路往后走，走到此路无路可走的时候，就再退回到岔路口，然后再去选另外的一条路走，每次走到此条路不通时就返回到上一个岔路口另选一条路走 ......经历这般 “摸爬滚打”之后，最后才可能走到出口。容易想到以同样的思路递归实现迷宫问题。

首先，还是先来做准备工作，定义一个全局的二维数组表示迷宫、一个结构体变量表示坐标，如下

简单的迷宫（没有回路）

如下：

用递归的思路，容易想到 :从入口点开始，在与它相邻各个方向中找出一可通的位置，然后跳至该处并把此位置的值置为2，然后重复以上操作，划分子问题，当最后到达规定的出口时停止算法。

代码如下：

 1 #pragma once
 2 #include <string.h>
 3 #define N 7
 4 int maze[N][N]={
 5     {0,0,0,0,0,0,0},
 6     {0,1,1,1,1,0,0},
 7     {0,1,0,0,0,0,0},
 8     {0,1,0,0,0,0,0},
 9     {0,1,1,1,1,0,0},
10     {0,1,0,0,1,1,1},
11     {0,1,0,0,0,0,0},
12 };
13 typedef struct Pos
14 {
15     int _col;
16     int _row;
17 }Pos;
18 
19 void PrintMaze(int arr[][N])
20 {
21     assert(arr);
22 
23     for(size_t i = 0; i< N; ++i)
24     {
25         for(size_t j = 0; j < N; ++j)
26             printf("%2d ", maze[i][j]);
27         printf("
");
28     }
29     printf("
");
30 }
31 int IsAccess(Pos cur, Pos next)
32 {
33     if(maze[next._row][next._col] == 1
34     && 0<= next._row && next._row < N
35     && 0<= next._col && next._col < N)
36     {
37         return 1;
38     }
39     return 0;
40 }
41 void GetPath(Pos cur)
42 {
43     Pos next = cur;
44     if(cur._col == N -1)  //找到出口
45     {
46         printf("出口:<%d, %d>
", cur._row, cur._col);
47         //return ;
48     }
49     maze[cur._row][cur._col] = 2;
50    //向右走
51     next = cur;
52     next._col+= 1;
53     if(IsAccess(cur, next))
54         GetPath(next);
55     //向上走
56     next = cur;
57     next._row-= 1;
58     if(IsAccess(cur, next))
59         GetPath(next);
60   //向下
61     next = cur;
62     next._row+= 1;
63     if(IsAccess(cur, next))
64         GetPath(next);
65     //向左
66     next = cur;
67     next._col-= 1;
68     if(IsAccess(cur, next))
69         GetPath(next);
70     
71 }

迷宫实现

上面代码可以找出可通的路线，但是对于有多条路线的迷宫，此种方式不能找出一条最短的那条路线，并不理想。

继续往下优化 ~_~ ...

带环的多条线路迷宫，选择路径最短的一条线路

有一种比较巧妙的办法：改变记录迷宫线路的方式来实现。

思路：改变记录走过位置的标记方式。当前坐标位置的标记值是上一个位置的标记值加1
得到；（假如某个位置走过了，被标记为了4，那么走过的下一个位置就将其标记为5... ）
与此同时，这样的记录方式还有一好处就是间接的表示了一条路径的长度。
由于改变了标记的方式，判断下个位置是否可通的条件做相应改变

判断可通条件：当前坐标的标记值 < 下一个坐标处的标记值或者下一个坐标标记值为 1

注意: 由于标记为 1的坐标也表示可通，所以初始时入口处坐标不妨从2开始标记。

实现代码：

 1 #include "Stack.h"   //上次实现的栈头文件
 2 
 3 int IsAccessInShortPath(Pos cur, Pos next)
 4 {
 5     if(( maze[cur._row][cur._col] < maze[next._row][next._col] || maze[next._row][next._col] == 1)
 6     && 0<= next._row && next._row < N
 7     && 0<= next._col && next._col < N )
 8     {
 9         return 1;
10     }
11     return 0;
12 }
13 Stack shortPath;   
14 void GetShortPath(Pos cur, Stack* pPath)
15 {
16     Pos next = cur;
17     if(StackEmpty(pPath) == 0)                 //初始入口位置 记为2
18         maze[cur._row][cur._col] = 2;
19     else
20     {
21         Pos prev = StackTop(pPath);     //当前位置标记值 为上一个位置标记值+1
22         maze[cur._row][cur._col] = maze[prev._row][prev._col] + 1;
23     }
24     StackPush(pPath, cur);
25     if(cur._col == N -1)  //找到出口
26     {
27         printf("出口:<%d, %d>
", cur._row, cur._col);
28         //每找到一条路线就和shortPath里的路线比较长短
29         //找到的路线更短，刷新shortPath
30         if(StackSize(pPath) < StackSize(&shortPath)
31             || StackEmpty(&shortPath) == 0)  //初始shortPath为空，需要刷新。
32         {
33             //不能直接shortPath._array = pPath->_array这样赋值
34             //shortPath._array = pPath->_array;
35             //shortPath._end = pPath->_top;
36             //shortPath._top = pPath->_top;
37             
38             if(shortPath._array)//刷新shortPath，由于每次额外开辟空间来保存较短路径
39                free(shortPath._array); //需要释放上一次开辟空间
40             shortPath._array = (DataType*)malloc(sizeof(DataType)* pPath->_top);
41             memcpy(shortPath._array, pPath->_array, sizeof(DataType) * pPath->_top);
42             shortPath._end = pPath->_top;
43             shortPath._top = pPath->_top;
44         }
45     }
46     //向上走
47     next = cur;
48     next._row-= 1;
49     if(IsAccessInShortPath(cur, next))
50         GetShortPath(next, pPath);
51     //向下
52     next = cur;
53     next._row+= 1;
54     if(IsAccessInShortPath(cur, next))
55         GetShortPath(next, pPath);
56      //左
57     next = cur;
58     next._col-= 1;
59     if(IsAccessInShortPath(cur, next))
60         GetShortPath(next, pPath);
61     //右
62     next = cur;
63     next._col+= 1;
64     if(IsAccessInShortPath(cur, next))
65         GetShortPath(next, pPath);
66     //四个方向都走不通 开始回朔，pop掉path栈里保存的路径坐标
67     StackPop(pPath);
68 }

改良版迷宫

递归的过程可参考下图：

最后再简单测一下：

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("入口
");
}

结果：

小结一下：

1.刷新shortPath里保存的路径，需要将path栈里存的路径整体拷贝过来。若将实现path栈底层的_array直接赋值给shortPath._array：

以本迷宫为例，它会先找到 ‘厂’ 型的路线，于是shortPath._array被赋值为path->_array，以此来保存路径；而在找第二条路径时当递归到<4, 5>处递归结束，说明这条路径更长 shortPath._array存放的内容应保持不变(即上一条路径)，但在回溯查找该条路经时，shortPath有出栈操作，shortPath._array里内容会被改动；而若是整体拷贝的话，每次都是新开辟空间来保持短路径，如若没到规定出口处，shortPath._array不会刷新，一直保存是一条最短的路径。

2.实现该迷宫时，默认设置出口为col = 6的位置，其实应该将出口的信息作为参数传入找路径的函数中，大家可以自行再优化。