C语言,使用栈来完成迷宫问题

栈是一种后进先出的数据结构，可以用来实现深度优先搜索（DFS）算法，从而解决迷宫问题。

下面是使用栈来完成迷宫问题的C语言代码：

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

#define ROWS 8
#define COLS 8

typedef struct {
    int x;  // 横坐标
    int y;  // 纵坐标
} Point;

// 迷宫地图
int map[ROWS][COLS] = {
    {0, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0, 1, 1, 0},
    {0, 1, 0, 0, 0, 1, 0, 0},
    {0, 1, 0, 1, 1, 1, 1, 0},
    {0, 1, 0, 0, 0, 0, 0, 0},
    {0, 1, 1, 1, 1, 1, 1, 0},
    {0, 0, 0, 0, 0, 0, 1, 0},
    {0, 0, 0, 0, 0, 0, 0, 0}
};

// 栈结构
typedef struct {
    Point *data;
    int top;
    int maxSize;
} Stack;

// 初始化栈
void initStack(Stack *s, int maxSize) {
    s->data = (Point *)malloc(sizeof(Point) * maxSize);
    s->top = -1;
    s->maxSize = maxSize;
}

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int isFull(Stack *s) {
    return s->top == s->maxSize - 1;
}

// 入栈
void push(Stack *s, Point elem) {
    if (isFull(s)) {
        return;
    }
    s->data[++s->top] = elem;
}

// 出栈
void pop(Stack *s) {
    if (isEmpty(s)) {
        return;
    }
    s->top--;
}

// 获取栈顶元素
Point top(Stack *s) {
    return s->data[s->top];
}

// DFS求解迷宫
void solveMaze() {
    // 初始化栈
    Stack s;
    Point start = {1, 1};
    initStack(&s, ROWS * COLS);
    push(&s, start);

    // 标记起点已经访问过
    map[start.x][start.y] = -1;

    while (!isEmpty(&s)) {
        Point current = top(&s);
        pop(&s);

        // 到达终点，输出路径
        if (current.x == ROWS - 2 && current.y == COLS - 2) {
            printf("(%d, %d)", current.x, current.y);
            while (!isEmpty(&s)) {
                current = top(&s);
                printf(" -> (%d, %d)", current.x, current.y);
                pop(&s);
            }
            printf("\n");
            return;
        }

        // 向下走
        if (map[current.x + 1][current.y] == 0) {
            Point next = {current.x + 1, current.y};
            push(&s, next);
            map[next.x][next.y] = -1;
        }

        // 向右走
        if (map[current.x][current.y + 1] == 0) {
            Point next = {current.x, current.y + 1};
            push(&s, next);
            map[next.x][next.y] = -1;
        }

        // 向上走
        if (map[current.x - 1][current.y] == 0) {
            Point next = {current.x - 1, current.y};
            push(&s, next);
            map[next.x][next.y] = -1;
        }

        // 向左走
        if (map[current.x][current.y - 1] == 0) {
            Point next = {current.x, current.y - 1};
            push(&s, next);
            map[next.x][next.y] = -1;
        }
    }

    // 没有找到路径
    printf("No solution!\n");
}

int main() {
    solveMaze();
    return 0;
}

代码中使用了一个结构体Point来表示迷宫中的一个坐标点，使用一个二维数组map来表示迷宫地图，其中0表示可以通过的路，1表示障碍物。

在求解过程中，首先将起点入栈，并标记为已访问。然后不断从栈中取出一个点，向四个方向扩展，如果扩展出的点是可以通过的路，则将其入栈并标记为已访问。当扩展出的点是终点时，输出路径。如果栈为空，表示没有找到路径。

这样，就使用栈完成了迷宫问题的求解。