迷宫求解【栈的应用或图的应用】 c语言

迷宫求解可以使用深度优先搜索（DFS）算法来实现，也可以使用广度优先搜索（BFS）算法来实现。

这里以使用栈的应用来实现迷宫求解。具体步骤如下：

1. 定义一个结构体来表示迷宫中的一个点，包括该点的坐标和是否被访问过的状态。

struct Point {
    int x; // 行坐标
    int y; // 列坐标
    int visited; // 是否被访问过
};

2. 读入迷宫的大小和迷宫地图，将其存储在一个二维数组中。

3. 定义一个栈来存储走过的路径。

4. 从起点开始，将其入栈。每次取出栈顶元素并判断是否为终点，如果是则输出路径并结束程序。如果不是，则将该点周围未走过的点入栈并标记为已访问。

5. 如果栈为空而未找到终点，则说明无解。

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

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

#define MAX_SIZE 10

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

struct Stack {
    struct Point arr[MAX_SIZE * MAX_SIZE];
    int top;
};

void stack_push(struct Stack *stack, struct Point point) {
    stack->arr[++stack->top] = point;
}

struct Point stack_pop(struct Stack *stack) {
    return stack->arr[stack->top--];
}

int stack_is_empty(struct Stack *stack) {
    return stack->top == -1;
}

int main() {
    int n, m; // 迷宫大小
    int map[MAX_SIZE][MAX_SIZE]; // 迷宫地图
    struct Point start, end; // 起点和终点
    struct Stack stack = { .top = -1 }; // 定义栈

    // 读入迷宫大小和地图
    printf("请输入迷宫大小（行数、列数）：");
    scanf("%d %d", &n, &m);
    printf("请输入迷宫地图：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
        }
    }

    // 读入起点和终点
    printf("请输入起点（行坐标、列坐标）：");
    scanf("%d %d", &start.x, &start.y);
    printf("请输入终点（行坐标、列坐标）：");
    scanf("%d %d", &end.x, &end.y);

    // 将起点入栈并标记为已访问
    start.visited = 1;
    stack_push(&stack, start);

    // 开始搜索迷宫
    while (!stack_is_empty(&stack)) {
        // 取出栈顶元素
        struct Point cur = stack_pop(&stack);

        // 判断是否为终点
        if (cur.x == end.x && cur.y == end.y) {
            // 输出路径
            printf("路径：\n");
            while (!stack_is_empty(&stack)) {
                struct Point path = stack_pop(&stack);
                printf("(%d,%d)\n", path.x, path.y);
            }
            printf("(%d,%d)\n", start.x, start.y);
            return 0;
        }

        // 将当前点周围未访问的点入栈
        if (cur.x > 0 && map[cur.x-1][cur.y] == 0) {
            struct Point next = { cur.x-1, cur.y, 1 };
            stack_push(&stack, next);
            map[cur.x-1][cur.y] = 1; // 标记为已访问
        }
        if (cur.x < n-1 && map[cur.x+1][cur.y] == 0) {
            struct Point next = { cur.x+1, cur.y, 1 };
            stack_push(&stack, next);
            map[cur.x+1][cur.y] = 1; // 标记为已访问
        }
        if (cur.y > 0 && map[cur.x][cur.y-1] == 0) {
            struct Point next = { cur.x, cur.y-1, 1 };
            stack_push(&stack, next);
            map[cur.x][cur.y-1] = 1; // 标记为已访问
        }
        if (cur.y < m-1 && map[cur.x][cur.y+1] == 0) {
            struct Point next = { cur.x, cur.y+1, 1 };
            stack_push(&stack, next);
            map[cur.x][cur.y+1] = 1; // 标记为已访问
        }
    }

    // 如果栈为空而未找到终点，则说明无解
    printf("无解！\n");

    return 0;
}