数据结构迷宫问题c语言

好的，迷宫问题可以使用深度优先搜索算法来解决。具体的步骤如下：

1. 定义一个二维数组作为迷宫地图，其中0表示障碍，1表示可以通过的路线。
2. 定义一个栈来存储路径，初始时将起点入栈。
3. 设定一个标志数组存储每个位置是否已经被访问过，初始时全部设置为false。
4. 设置一个方向数组，表示每个位置可以往哪些方向走。
5. 从栈顶取出一个元素，判断它是否为终点，如果是则输出路径并结束程序。
6. 如果不是终点，则遍历该位置的所有可行方向，按照顺序依次入栈，并将该位置标记为已访问。
7. 如果所有方向都无法到达终点，则弹出该位置并回溯到上一个位置，继续遍历它的其他方向。
8. 重复以上步骤直到找到终点或栈为空。

以下是一份简单的代码示例：

#include <stdio.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,1,0,0,0,1,0,0,1},
    {1,0,1,1,1,0,1,0,1,1},
    {1,0,0,0,1,0,1,0,0,1},
    {1,0,1,0,0,1,1,1,0,1},
    {1,0,1,1,1,1,0,1,0,1},
    {1,0,0,0,0,0,0,1,0,1},
    {1,0,1,1,1,1,1,1,0,1},
    {1,0,0,0,0,0,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1}
};

bool visited[ROW][COL] = {false};

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

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

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

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

Point pop(Stack *s) {
    return s->data[s->top--];
}

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

bool is_valid(Point p) {
    return p.x >= 0 && p.x < ROW && p.y >= 0 && p.y < COL && maze[p.x][p.y] == 1 && !visited[p.x][p.y];
}

void dfs(Point start, Point end) {
    Stack s;
    init(&s);
    push(&s, start);
    visited[start.x][start.y] = true;

    while (!is_empty(&s)) {
        Point cur = pop(&s);
        if (cur.x == end.x && cur.y == end.y) {
            printf("找到了一条路径：");
            for (int i = 0; i <= s.top; i++) {
                printf("(%d,%d) ", s.data[i].x, s.data[i].y);
            }
            printf("(%d,%d)\n", cur.x, cur.y);
            return;
        }

        Point dirs[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0; i < 4; i++) {
            Point next = {cur.x + dirs[i].x, cur.y + dirs[i].y};
            if (is_valid(next)) {
                push(&s, next);
                visited[next.x][next.y] = true;
            }
        }
    }

    printf("没有找到路径。\n");
}

int main() {
    Point start = {1, 1};
    Point end = {8, 8};
    dfs(start, end);
    return 0;
}

在这个示例中，我们使用了一个栈来存储路径，使用一个标志数组来记录哪些位置已经访问过。我们也定义了一个is_valid函数来判断某个位置是否符合要求。在dfs函数中，我们使用一个循环来遍历栈中的每个元素，并按照顺序遍历它的四个方向。当找到终点时，我们输出整个路径，否则继续遍历。如果整个栈都遍历完了还没有找到终点，则输出“没有找到路径”。