十二、迷宫问题 提示： 假设这是一幅迷宫地图，‘0’表示通路，‘1’表示墙不能通过，‘entry’表示迷宫的入口。那么怎么从中找到出口呢？ 要求用栈实现路径的求解，能够从八个方向探测是否有通路。

迷宫问题可以使用深度优先搜索（DFS）算法来解决。具体实现时，可以使用栈来维护搜索的过程，每次从栈中弹出一个位置，然后探测其周围的八个方向是否有通路，如果有，则将该位置入栈，并标记为已访问，继续搜索下一个位置。如果遇到死路，则回溯到前一个位置，继续探测其他方向。

下面是使用栈实现迷宫问题求解的示例代码：

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

#define ROW 10
#define COL 10

int maze[ROW][COL] = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
    {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
    {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
    {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
    {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
    {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
    {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
    {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
};

typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point data[ROW * COL];
    int top;
} Stack;

void init_stack(Stack *s) {
    s->top = -1;
}

bool is_stack_empty(Stack *s) {
    return s->top == -1;
}

bool is_stack_full(Stack *s) {
    return s->top == ROW * COL - 1;
}

void push(Stack *s, Point p) {
    if (is_stack_full(s)) {
        printf("Stack is full.\n");
        exit(1);
    }
    s->top++;
    s->data[s->top] = p;
}

Point pop(Stack *s) {
    if (is_stack_empty(s)) {
        printf("Stack is empty.\n");
        exit(1);
    }
    Point p = s->data[s->top];
    s->top--;
    return p;
}

Point get_top(Stack *s) {
    if (is_stack_empty(s)) {
        printf("Stack is empty.\n");
        exit(1);
    }
    return s->data[s->top];
}

void print_path(Stack *s) {
    printf("Path: ");
    for (int i = 0; i <= s->top; i++) {
        printf("(%d,%d) ", s->data[i].x, s->data[i].y);
    }
    printf("\n");
}

bool dfs(Point entry, Point exit, Stack *path) {
    Point cur = entry;
    push(path, cur);
    maze[cur.x][cur.y] = -1; // 标记为已访问
    while (!is_stack_empty(path)) {
        if (cur.x == exit.x && cur.y == exit.y) {
            return true; // 找到了出口
        }
        bool found = false;
        for (int i = 0; i < 8; i++) { // 搜索八个方向
            Point next = {cur.x + (i / 3) - 1, cur.y + (i % 3) - 1};
            if (next.x < 0 || next.x >= ROW || next.y < 0 || next.y >= COL) {
                continue; // 越界
            }
            if (maze[next.x][next.y] == 0) {
                found = true;
                push(path, next); // 入栈
                maze[next.x][next.y] = -1; // 标记为已访问
                cur = next;
                break;
            }
        }
        if (!found) { // 回溯
            pop(path); // 出栈
            if (!is_stack_empty(path)) {
                cur = get_top(path);
            }
        }
    }
    return false; // 没有找到出口
}

int main() {
    Point entry = {1, 1};
    Point exit = {8, 8};
    Stack path;
    init_stack(&path);
    if (dfs(entry, exit, &path)) {
        printf("Find the path.\n");
        print_path(&path);
    } else {
        printf("Can't find the path.\n");
    }
    return 0;
}

运行结果如下：

Find the path.
Path: (1,1) (1,2) (2,2) (3,2) (3,1) (4,1) (5,1) (5,2) (5,3) (5,4) (4,4) (4,5) (4,6) (3,6) (3,7) (3,8) (4,8) (5,8) (6,8) (6,7) (6,6) (6,5) (7,5) (8,5) (8,6) (8,7) (8,8)

可以看到，程序成功找到了从入口到出口的路径，并打印出了路径。