C语言迷宫求解数据结构

以下是C语言实现迷宫求解的数据结构和算法：
1. 数据结构：
- 迷宫地图：使用二维数组表示，0表示可以通过，1表示障碍物。
- 栈：用于存储走过的路径。
- 路径：用一个结构体表示，包含坐标和方向信息。
2. 算法：
- 初始化：将迷宫地图和栈初始化。
- 入口：将入口压入栈中。
- 循环：从栈中取出一个路径，判断是否到达出口，如果到达则输出路径并结束，否则按照上、右、下、左的顺序依次探索相邻的四个方向，如果可以通过则将新路径压入栈中。
- 结束：如果栈为空，则说明无解。

以下是C语言实现迷宫求解的代码示例：

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

#define ROW 10
#define COL 10

// 定义路径结构体
typedef struct {
    int x; // 行坐标
    int y; // 列坐标
    int dir; // 方向
} Path;

// 定义栈结构体
typedef struct {
    Path data[ROW * COL];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

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

// 入栈
void push(Stack *s, Path p) {
    s->top++;
    s->data[s->top] = p;
}

// 出栈
Path pop(Stack *s) {
    Path p = s->data[s->top];
    s->top--;
    return p;
}

// 判断是否到达出口
int isExit(Path p, int maze[][COL]) {
    return p.x == ROW - 1 && p.y == COL - 1 && maze[p.x][p.y] == 0;
}

// 判断是否可以通过
int isPass(Path p, int maze[][COL]) {
    return p.x >= 0 && p.x < ROW && p.y >= 0 && p.y < COL && maze[p.x][p.y] == 0;
}

// 迷宫求解
void mazePath(int maze[][COL]) {
    Stack s;
    Path p = {0, 0, -1}; // 入口
    Path next;
    initStack(&s);
    push(&s, p);
    while (!isEmpty(&s)) {
        p = pop(&s);
        p.dir++;
        while (p.dir < 4) {
            switch (p.dir) {
                case 0: next.x = p.x - 1; next.y = p.y; break; // 上
                case 1: next.x = p.x; next.y = p.y + 1; break; // 右
                case 2: next.x = p.x + 1; next.y = p.y; break; // 下
                case 3: next.x = p.x; next.y = p.y - 1; break; // 左
            }
            if (isExit(next, maze)) { // 到达出口
                printf("(%d,%d)", p.x, p.y);
                printf(" -> (%d,%d)\n", next.x, next.y);
                return;
            }
            if (isPass(next, maze)) { // 可以通过
                push(&s, p);
                p = next;
                p.dir = -1;
                maze[p.x][p.y] = 1; // 标记已走过
            }
            p.dir++;
        }
    }
    printf("No path!\n"); // 无解
}

int main() {
    int maze[ROW][COL] = {
        {0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
        {0, 1, 0, 1, 1, 1, 0, 1, 0, 1},
        {0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
        {0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
        {0, 1, 0, 1, 1, 1, 1, 1, 1, 1},
        {0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 0}
    };
    mazePath(maze);
    return 0;
}