用栈的方法来走迷宫

beyes

走迷宫的方法，可以用栈，也可以用递归来实现。用栈的方法基本思路是：先设立一套行进测试方案，比如按照上、下、左、右依次进行道路的测试，如果遇到走得通的坐标，就对此坐标设立一个能走通的标志，同时将此坐标入栈保存起来，以便后面可能进行的回溯操作。回溯表示，当走进死胡同时，要按照原路返回，那么在返回时。回溯的行为其实是出栈操作，在对一个坐标进行出栈操作时，要同时对这个坐标做个“回溯”标记，这样，在返回原来地点时，就不会再次重复对走过的路进行测试而进入死循环。

测试代码：

#include <stdio.h>
#include <stdlib.h>

struct stack_node {            /*栈的结构声明*/
    int x;                /*路径坐标x*/
    int y;                /*路径坐标y*/
    struct stack_node *next;    /*指向下一结点*/
};


typedef struct stack_node stack_list;    /*链表新类型*/
typedef stack_list *link;        /*链表指针新类型*/

link path = NULL;            /*路径栈指针*/

/*------------------------*/
/*栈数据的存入            */
/*------------------------*/
link push (link stack, int x, int y)
{
    link new_node;
   
    /*分配结点内存*/
    new_node = (link) malloc (sizeof (stack_list));
    if (!new_node) {
        printf ("内存分配失败! \n");
        return NULL;
    }
   
    new_node->x = x;        /*存入路径坐标x*/
    new_node->y = y;        /*存入路径坐标y*/
    new_node->next = stack;        /*新结点指向原栈顶结点*/
    stack = new_node;        /*stack指向栈顶结点*/
   
    return (stack);
}

/*------------------------*/
/*栈数据的取出            */
/*------------------------*/
link pop (link stack, int *x, int *y)
{
    link top;            /*指向栈顶端*/

    if (stack != NULL) {
        top = stack;        /*指向栈顶端*/
        stack = stack->next;    /*出栈后的新栈顶*/
        *x = stack->x;       
        *y = stack->y;        /*新栈顶坐标*/
       
        free (top);        /*释放原栈顶*/
        return (stack);        /*返回栈指针*/
    } else *x = -1;
}

int main ()
{
    int maze [7][10] = {        /*迷宫数组*/
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 0, 1, 0, 1, 0, 0, 0, 0, 1,
        1, 0, 1, 0, 1, 0, 1, 1, 0, 1,
        1, 0, 1, 0, 1, 1, 1, 0, 0, 1,
        1, 0, 1, 0, 0, 0, 0, 0, 1, 1,
        1, 0, 0, 0, 1, 1, 1, 0, 0, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };


    int i, j;
    int x = 5;
    int y = 8;            /*迷宫入口坐标*/

    while (x != 1 || y != 1) {    /*迷宫出口坐标(1,1)*/
        maze [x][y] = 2;    /*用数字2标示走过的路*/
       
        if (maze [x-1][y] == 0) {        /*向上走*/
            x = x - 1;
            path = push (path, x, y);    /*可以走,存入路径*/
        }
        else if (maze [x+1][y] == 0) {        /*向下走*/
            x = x + 1;
            path = push (path, x, y);
        }    else if (maze [x][y-1] == 0) {    /*往左走*/
            y = y - 1;
            path = push (path, x, y);
             }    else if (maze [x][y+1] == 0) {
                y = y + 1;
                path = push (path, x, y);
            } else {            /*没有路可走了,回溯*/
                maze [x][y] = 3;
                path = pop (path, &x, &y);
            }           
    }
    maze [x][y] = 2;
    printf ("迷宫的路径如下图所示:\n");
    for (i = 1; i < 6; i++) {
        for (j = 1; j < 9; j++)
            printf ("%d", maze [i][j]);
        printf ("\n");
    }

    return (0);
}

运行与输出(迷宫路径)：

beyes@linux-beyes:~/C/structer> ./maze.exe
迷宫的路径如下图所示:
21313333
21313113
21311133
21222221
22211122

红色部分表示正确的走出迷宫路径，蓝色的 3 表示曾经行进过的路径但由于道路不同而进行了回溯。