用栈求解迷宫问题C语言

在C语言中，用栈来解决迷宫问题通常采用深度优先搜索（Depth-First Search, DFS）算法的一种变形，称为广度优先搜索（Breadth-First Search, BFS）。这里以BFS为例，因为它的思路更直观，适合使用栈的数据结构。 BFS的基本步骤是： 1. 将起始位置（通常是迷宫的第一个空格或入口）入栈，并标记为已访问。 2. 当栈非空时，弹出栈顶元素。检查其相邻的未访问节点（上下左右），如果它们是出口，则找到解决方案；否则将这些邻居压入栈并标记为已访问。 3. 重复步骤2，直到找到出口或栈为空，后者意味着无解。 以下是简化版的C语言代码实现： ```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; } ```