c语言用栈的方法求迷宫路径

求解迷宫路径可以使用深度优先搜索算法，而栈可以作为深度优先搜索算法的辅助数据结构。具体实现步骤如下：

1. 定义一个栈结构体，包含栈顶指针和栈中元素数组。
2. 定义一个结构体表示迷宫的位置，包含行列坐标和该位置是否为障碍物的标志。
3. 从起点开始，将起点入栈。
4. 循环执行以下步骤：
* 如果栈为空，则退出循环。
* 取出栈顶元素，如果该元素为终点，则说明已经找到了一条路径，输出路径并退出循环。
* 否则，遍历该元素的四个相邻位置，如果该位置为通路且未访问过，则将该位置入栈，并标记为已访问。
5. 如果没有找到路径，则输出无解。

下面是使用C语言实现求解迷宫路径的代码示例：

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

#define MAZE_SIZE 10

typedef struct {
    int row;
    int col;
    int is_obstacle;
} Position;

typedef struct {
    Position *elements;
    int top;
} Stack;

void init_stack(Stack *stack, int size)
{
    stack->elements = (Position *)malloc(size * sizeof(Position));
    stack->top = -1;
}

void push(Stack *stack, Position pos)
{
    stack->elements[++stack->top] = pos;
}

Position pop(Stack *stack)
{
    return stack->elements[stack->top--];
}

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

int is_visited(int visited[][MAZE_SIZE], int row, int col)
{
    return visited[row][col];
}

void mark_visited(int visited[][MAZE_SIZE], int row, int col)
{
    visited[row][col] = 1;
}

int is_obstacle(Position pos)
{
    return pos.is_obstacle;
}

int is_valid_position(int row, int col)
{
    return row >= 0 && row < MAZE_SIZE && col >= 0 && col < MAZE_SIZE;
}

void print_path(Stack *stack)
{
    printf("Found path:\n");
    for (int i = 0; i <= stack->top; i++) {
        printf("(%d, %d)\n", stack->elements[i].row, stack->elements[i].col);
    }
}

void find_path(int maze[][MAZE_SIZE], Position start, Position end)
{
    Stack stack;
    int visited[MAZE_SIZE][MAZE_SIZE] = {0};

    init_stack(&stack, MAZE_SIZE * MAZE_SIZE);
    push(&stack, start);

    while (!is_empty(&stack)) {
        Position curr = pop(&stack);

        if (curr.row == end.row && curr.col == end.col) {
            print_path(&stack);
            return;
        }

        mark_visited(visited, curr.row, curr.col);

        int row = curr.row, col = curr.col - 1;  // left
        if (is_valid_position(row, col) && !is_visited(visited, row, col) && !is_obstacle((Position){row, col, maze[row][col]})) {
            push(&stack, (Position){row, col, 0});
        }

        row = curr.row - 1, col = curr.col;  // up
        if (is_valid_position(row, col) && !is_visited(visited, row, col) && !is_obstacle((Position){row, col, maze[row][col]})) {
            push(&stack, (Position){row, col, 0});
        }

        row = curr.row, col = curr.col + 1;  // right
        if (is_valid_position(row, col) && !is_visited(visited, row, col) && !is_obstacle((Position){row, col, maze[row][col]})) {
            push(&stack, (Position){row, col, 0});
        }

        row = curr.row + 1, col = curr.col;  // down
        if (is_valid_position(row, col) && !is_visited(visited, row, col) && !is_obstacle((Position){row, col, maze[row][col]})) {
            push(&stack, (Position){row, col, 0});
        }
    }

    printf("No path found.\n");
}

int main()
{
    int maze[MAZE_SIZE][MAZE_SIZE] = {
        {0, 0, 0, 1, 0, 1, 1, 1, 0, 1},
        {1, 1, 0, 1, 0, 0, 0, 1, 0, 0},
        {0, 1, 0, 0, 1, 0, 1, 1, 1, 1},
        {0, 1, 1, 1, 1, 0, 1, 0, 0, 1},
        {0, 0, 0, 0, 0, 1, 0, 0, 1, 0},
        {1, 1, 1, 1, 0, 1, 1, 1, 1, 0},
        {0, 0, 0, 1, 0, 0, 0, 0, 0, 1},
        {1, 1, 0, 1, 1, 1, 1, 1, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 0}
    };

    Position start = {0, 0, 0};
    Position end = {9, 9, 0};
    find_path(maze, start, end);

    return 0;
}

其中，迷宫地图使用一个二维数组表示，1表示障碍物，0表示通路。起点和终点分别用一个Position结构体表示，is_obstacle字段表示该位置是否为障碍物。深度优先搜索算法使用栈作为辅助数据结构，visited二维数组用于记录每个位置是否已经被访问过。