用栈求解迷宫问题C语言

在C语言中，用栈来解决迷宫问题通常采用深度优先搜索（Depth-First Search, DFS）算法的一种变形，称为广度优先搜索（Breadth-First Search, BFS）。这里以BFS为例，因为它的思路更直观，适合使用栈的数据结构。

BFS的基本步骤是：
1. 将起始位置（通常是迷宫的第一个空格或入口）入栈，并标记为已访问。
2. 当栈非空时，弹出栈顶元素。检查其相邻的未访问节点（上下左右），如果它们是出口，则找到解决方案；否则将这些邻居压入栈并标记为已访问。
3. 重复步骤2，直到找到出口或栈为空，后者意味着无解。

以下是简化版的C语言代码实现：

#include <stdio.h>
#include <stdlib.h>
#define ROW 5 // 迷宫行数
#define COL 5 // 迷宫列数

typedef enum {EMPTY = 0, WALL, START, END} Tile; // 定义迷宫状态枚举

// 判断当前位置是否越界或墙
int is_valid(int row, int col) {
    return row >= 0 && row < ROW && col >= 0 && col < COL && maze[row][col] != WALL;
}

// 助手函数，用于处理栈操作
void push(Tile* maze, int row, int col, Stack* stack) {
    if (is_valid(row, col)) {
        maze[row][col] = START; // 标记为起点
        stack->top++;
        stack->data[stack->top] = (row << 8) | col; // 存储坐标
    }
}

// 解决迷宫
Tile* solve_maze(Tile* maze, Stack* stack, int start_row, int start_col) {
    // 初始化相关变量
    int end_row = -1, end_col = -1;
    stack->top = 0;

    // 入栈起点
    push(maze, start_row, start_col, stack);

    while (stack->top > 0) {
        int current_row = ((stack->data[stack->top]) >> 8);
        int current_col = stack->data[stack->top] & 0xFF;
        stack->top--;

        // 检查邻居
        if (maze[current_row][current_col] == END) {
            end_row = current_row;
            end_col = current_col;
            break;
        } else if (maze[current_row][current_col] == EMPTY) {
            // 推动其他可走的邻居
            if (current_row > 0 && is_valid(current_row - 1, current_col))
                push(maze, current_row - 1, current_col, stack);
            if (current_row + 1 < ROW && is_valid(current_row + 1, current_col))
                push(maze, current_row + 1, current_col, stack);
            if (current_col > 0 && is_valid(current_row, current_col - 1))
                push(maze, current_row, current_col - 1, stack);
            if (current_col < COL - 1 && is_valid(current_row, current_col + 1))
                push(maze, current_row, current_col + 1, stack);
        }
    }

    // 返回解决方案
    if (end_row != -1)
        return maze + (end_row * COL) + end_col;
    else
        return NULL; // 无解
}

// 主函数
int main() {
    Tile maze[ROW][COL] = {{WALL, WALL, EMPTY, WALL, WALL},
                           {WALL, EMPTY, EMPTY, EMPTY, WALL},
                           {WALL, EMPTY, START, EMPTY, WALL},
                           {WALL, EMPTY, EMPTY, END, WALL},
                           {WALL, WALL, EMPTY, EMPTY, WALL}};
    Stack stack;
    stack.top = 0;

    // 调用solve_maze获取解决方案
    Tile* solution = solve_maze(maze, &stack, 2, 1); // 起点在第3行第2列

    // 输出解决方案
    if (solution)
        printf("Solution found at %d, %d\n", solution->row, solution->col);
    else
        printf("No solution exists.\n");

    return 0;
}