用C语言代码编写程序实现“栈求解迷宫”

在C语言中，我们可以使用栈数据结构来解决迷宫问题，因为栈的特性符合回溯搜索（Backtracking）的思想，通常用于遍历和寻找路径。下面是一个简单的迷宫求解算法的C语言代码示例，使用深度优先搜索（DFS）：

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

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

// 定义迷宫数组，0表示墙，1表示可以通行的空格
int maze[5][5] = {
    {1, 1, 1, 1, 0},
    {0, 1, 0, 0, 1},
    {1, 0, 1, 1, 1},
    {1, 1, 0, 0, 0},
    {0, 0, 0, 1, 1}
};

// 检查当前位置是否越界，是否是墙壁，或者已经访问过
int is_valid(int row, int col) {
    return row >= 0 && row < 5 && col >= 0 && col < 5 && maze[row][col] == 1;
}

// 动态分配栈空间，存储位置信息
Position* create_position_stack() {
    int stack_size = 0;
    Position* stack = (Position*)malloc(sizeof(Position) * stack_size);
    return stack;
}

// 将位置压入栈
void push_stack(Position* stack, int row, int col) {
    stack[stack_size++] = (Position){row, col};
}

// 弹出栈顶元素并返回
Position pop_stack(Position* stack) {
    if(stack_size > 0) {
        Position temp = stack[stack_size - 1];
        stack_size--;
        return temp;
    }
    return (Position){-1, -1}; // 如果栈为空则返回无效位置
}

// 深度优先搜索，从起点开始
void dfs(Position start) {
    Position stack[5]; // 假设最大步数不超过5x5迷宫
    Position current = start;
    
    while(1) {
        push_stack(stack, current.row, current.col); // 入栈当前节点
        if(current.row == 4 && current.col == 4) { // 到达终点
            printf("Path found: %d %d -> %d %d\n", 
                   start.row, start.col, current.row, current.col);
            break;
        }

        // 四个相邻方向检查
        for(int dir = 0; dir < 4; dir++) {
            int newRow = current.row + directions[dir][0];
            int newCol = current.col + directions[dir][1];

            if(is_valid(newRow, newCol)) {
                current.row = newRow;
                current.col = newCol;
                break;
            }
        }

        if(stack_size > 0) { // 栈非空，取出上一步
            current = pop_stack(stack);
        } else { // 栈为空，无路可走
            printf("No path found.\n");
            return;
        }
    }
}

int main() {
    dfs((Position){0, 0}); // 从起点(0,0)开始搜索
    return 0;
}