栈的妙用-实现迷宫问题

堆栈是计算机程序中非常重要的一部分，主要用来参数的调用，局部变量的存储等，在C语言中的函数调用过程中通过不同函数的堆栈空间可以非常方便的找到传递进来的参数以及退出时应该返回的地址。具体的参看“函数调用分析 ”，这篇文章中通过实例分析讨论了函数调用过程中堆栈的变化过程。

实质上栈的运用并不是只能在函数调用中，栈作为一种数据结构，自然有其特殊的意义，栈的最大特点是"先入后出，后入先出"，这个特点可以用来结局很多的问题。C语言中的函数调用算是其中的最主要的用法之一，也就不再分析和讨论。同样递归，嵌套调用等都属于函数调用的子类也不再描述。在其他方面经典的运用是解决迷宫问题，不同进制数值之间的转换，长字符串的分解以及算术表达式的求值等。下面我主要采用栈实现经典的迷宫问题。

迷宫问题

迷宫问题是经典的一类问题，如何从给出的入口找到对应的出口，实现的方法和马踏棋盘问题相似也是通过找到周围8个方向坐标的关系，然后依据深度优先搜索方法和一定的条件找到下一步对应的出路。由于迷宫问题需要存储具体的完成路劲，这与前面的问题存在一定的差别。采用栈能够很好的解决这个问题，其中栈结构用来存储具体的坐标和方向。这样根据栈就能保证以后每一次都能快速的找到出路。

实现的基本步骤如下：

1、为了避免边界检测问题，在迷宫的外围添加一层围墙，比如原来的迷宫为m*n,则添加围墙以后的矩阵为(m+2)*(n+2)。其中为1表示不能走通，0时表示可以走通。这样maze[1][1]表示迷宫的入口，而maze[m][n]表示迷宫的出口。

2、创建一个堆栈空间，可以采用静态数组的方式，但由于不能准确的估计数组空间大小，可以采用动态创建的方式。并将入口坐标值压入到栈中。定义一个与迷宫大小相同的矩阵mark，用来统计当前坐标是否已经到达过，当没有到达坐标（i,j）时，则有mark[i][j] = 0,如果之前到达过，则有mark[i][j] = 1.这样主要是为了避免形成内部死循环，同时说明此路不能走通。

3、检测栈空间是否为空，如果为空则停止，如果不为空，则弹出栈顶的元素.

4、采用循环的方式，依据元素的方向确定下一个坐标，具体的确定方法依据之前的移动关系找到，判断该位置是否为0（maze[nextrow][nextcol] == 0）以及之前是否到达该位置(mark[nextrow][nextcol] == 1)。如果满足条件，则将mark[nextrow][newcol]设置为1，并将当前位置以及具体的方向值压入栈中，将当前坐标设置为之前确定的下一个坐标，设置方向为0。然后重新进行步骤4。如果8个方向全部不能找到合适的下一个坐标，说明此路走不通。重新进行步骤3，探索新的路劲。探索成功的条件是(nextrow == EXIT_ROW&&nextcol == EXIT_COL)。

基本的实现流程图如下所示：

代码实现如下：

    /*maze_problem.h*/
    #ifndef MAZE_PROBLEM_H_H_
    #define MAZE_PROBLEM_H_H_

    typedef struct
    {
        int vert;
        int horiz;
    }offsets;

    typedef struct {
        int row;
        int col;
        int dir;
    }element;

    typedef struct {
        int row;
        int col;
    }coordinate;
    #endif

/*maze_problem.c*/
#include "maze_problem.h"

#include
#include

offsets move[8];

    /*the stack save the path, and used */
    element * stack;
    int top = -1;

    void initial_move(void)
    {
        /*horiz means cols*/
        move[0].horiz = 0;
        /*vert means rows*/
        move[0].vert = -1;

        move[1].horiz = 1;
        move[1].vert = -1;

        move[2].horiz = 1;
        move[2].vert = 0;

        move[3].horiz = 1;
        move[3].vert = 1;

        move[4].horiz = 0;
        move[4].vert = 1;

        move[5].horiz = -1;
        move[5].vert = 1;

        move[6].horiz = -1;
        move[6].vert = 0;

        move[7].horiz = -1;
        move[7].vert = -1;
    }
    #define MAZE_ROWS    12
    #define MAZE_COLS    15

    #define NEW_MAZE_ROWS (MAZE_ROWS + 2)
    #define NEW_MAZE_COLS (MAZE_COLS + 2)
    #define EXIT_COL    15
    #define EXIT_ROW    12

    int maze[NEW_MAZE_ROWS][NEW_MAZE_COLS]
    = {
     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
     1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1,
     1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1,
     1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,
     1,1,1,0,1,1,1,1,1,1,1,0,1,1,0,0,1,
     1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,
     1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1,
     1,0,0,1,1,0,1,1,1,0,1,0,0,1,0,1,1,
     1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,
     1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,
     1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1,
     1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1,
     1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,
     1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
    };

/*used to store the used place*/
int mark[NEW_MAZE_ROWS][NEW_MAZE_COLS];

    void mark_init()
    {
        int i = 0,j = 0;
        for(i = 0; i < NEW_MAZE_ROWS ; ++ i)
            for(j = 0; j < NEW_MAZE_COLS ; ++ j)
                mark[i][j] = 0;
    }
    int mark_stack_size(int maze[NEW_MAZE_ROWS][NEW_MAZE_COLS])
    {
        int i = 0,j = 0;

        int size = 0;
        for(i = 0; i < NEW_MAZE_ROWS; ++ i)
            for (j = 0; j < NEW_MAZE_COLS ; ++ j)
            {
                if(!maze[i][j])
                size ++;
            }
        return size;
    }

    coordinate nextposition(element a,int dir)
    {
        coordinate b;
        b.col = a.col + move[dir].horiz;
        b.row = a.row + move[dir].vert;

        return b;
    }

    int maze_out()
    {
        element temp;
        coordinate nextp;

        /*Test the stack is not empty*/
        while(top >= 0)
        {
            /*pop a element*/
            temp = *(stack+top);
            top --;

            /*find on eight directions*/
            while(temp.dir < 8)
            {
                /*get the possible next positions*/
                nextp = nextposition(temp,temp.dir);
                /*next direction*/
                temp.dir ++;

                /*success conditions*/
                if(nextp.row == EXIT_ROW &&
                 nextp.col == EXIT_COL)
                {
                    /*save current position*/
                    stack[++top] = temp;

                    /*save the exit pointion*/
                    stack[++top].row = EXIT_ROW;
                    stack[top].col = EXIT_COL;
                    stack[top].dir = 0;

                    /*exit*/
                    return 1;
                }

                /*the new position is ok and does not wake*/
                if(maze[nextp.row][nextp.col] ==0 &&
                 mark[nextp.row][nextp.col] == 0)
                {
                    /*mark means that this way has been waked*/
                    mark[nextp.row][nextp.col] = 1;

                    /*
                     *push a element in stack
                     *save current position and direction
                     *if this way is failed, used to this position to start new way.
                    */
                    stack[++top] = temp;

                    /*go to the new position as current position*/
                    temp.row = nextp.row;
                    temp.col = nextp.col;
                    temp.dir = 0;
                }
            }
        }
        /*failed*/
        return 0;
    }

    int main()
    {
        int i = 0;
        /*inital the mark array*/
        mark_init();
        initial_move();

        /*create stack*/
        stack = (element*)malloc(mark_stack_size(maze)*sizeof(element));
        /*if failed*/
        if(stack == NULL)
            return 0;
        /*push a element in stack*/
        top ++;
        (stack+top)->col = 1;
        (stack+top)->row = 1;
        (stack+top)->dir = 0;

        if(maze_out())
        {
            while(i <= top)
            {
                printf("(%d,%d,%d)\n",stack[i].row,stack[i].col,stack[i].dir);
                i ++;
            }
        //    printf("(%d,%d)\n",EXIT_ROW,EXIT_COL);

        }
        /*free the memory*/
        free(stack);
        /*point to the NULL*/
        stack = NULL;
        return 1;
    }

测试结果：