【栈的应用】迷宫算法（栈和回溯思想）

人生，就像一个很大的栈演变。出生时赤条条地来到这个世界，慢慢地长大，渐渐地变老，最终还得赤条条地离开世间。web

思路分析：

上面是一个迷宫地图，在地图上，0 表明墙，1 表明通路。算法

迷宫是回溯法和栈的综合应用。svg

下面给出完整的思路和寻路算法：spa

这里咱们只研究一种状况：地图只有一条路径能够出去。

寻路算法按照上下左右的顺序进行遍历和判断。

从入口出发，按照上下左右的顺序寻路，每次的路径坐标Pos放到栈中，存放坐标是为了方便回溯。如上图，直到向上没有通路了，再查看当前位置，左，右是否有通路，实际如图所示，没有。那么就取栈顶坐标，回退一步，再查看左右是否有通路。如此循环。code

若是不停地回退，致使栈中没有元素，这就说明回退到了迷宫入口。那么就能够说明此迷宫没有通路。regexp

在迷宫中还有一点值得注意就是对是否为地图边界 的判断。xml

下面给出核心代码：

迷宫定义：blog

#define N 10
typedef struct Pos{
    int _row;
    int _col;
}Pos;

typedef struct Maze
{
    int _mz[N][N];
    Pos _entry;
}Maze;

寻路算法：图片

int CheckIsAccess(Maze *m, Pos pos)
{
    if(pos._row >= 0 && pos._row < N
       && pos._col >= 0 && pos._col < N
       && m->_mz[pos._row][pos._col] == 1)
       {
           return 1;
       }
       return 0;
}


void MazeGetPath(Maze* m)
{
    Stack s;
    StackInit(&s, 10);
    StackPush(&s, m->_entry);

    while(StackEmpty(&s) != 0)
    {
        //1,入口   2，下一个能够走的位置  3，回溯的上一个位置
        cur = StackTop(&s);
        m->_mz[cur._row][cur._col] = 2;

        if(cur._col == N-1)
        {
            printf("找到通路了\n");
            return;
        }

        Pos next = cur;

        //上
        next._row -= 1;
        if(CheckIsAccess(m, next) == -1)
        {
            StackPush(&s, next);
            continue;
        }

        //下
        next = cur;
        next._row += 1;
        if(CheckIsAccess(m, next) == 1)
        {
            StackPush(&s, next);
            continue;
        }

        //左
        next = cur;
        next._col -= 1;
        if(CheckIsAccess(m, next) == 1)
        {
            StackPush(&s, next);
            continue;
        }

        //右
        next = cur;
        next._col += 1;
        if(CheckIsAccess(m, next) == 1)
        {
            StackPush(&s, next);
            continue;
        }

        //回溯
        StackPop(&s);
    }
    printf("没有通路\n");
}