栈的妙用-实现迷宫问题

 
实质上栈的运用并不是只能在函数调用中，栈作为一种数据结构，自然有其特殊的意义，栈的最大特点是"先入后出，后入先出"，这个特点可以用来结局很多的问题。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,
    };[page]

    /*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) ",stack[i].row,stack[i].col,stack[i].dir);
                i ++;
            }
        //    printf("(%d,%d) ",EXIT_ROW,EXIT_COL);

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

测试结果：

在迷宫问题中，栈主要实现了对满足条件坐标以及方向值(0-7,分别表示一个具体的方向)的动态保存能够保证路劲的一致性，也就是先入后出的特性。