用栈的方法来走迷宫 - 曲径通幽论坛

#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);
}