7-33 地下迷宫探索 c语言

### 地下迷宫探索的C语言实现 地下迷宫探索通常可以通过图的遍历来解决，常见的方法有深度优先搜索（DFS）和广度优先搜索（BFS）。以下是基于引用中的相关内容以及标准算法设计的一个示例代码。 #### 1. 数据结构定义 为了表示迷宫，可以使用二维数组来模拟地图。其中，“0”代表可通行路径，“1”代表障碍物或墙壁。“S”表示起点，“E”表示终点。 ```c #include <stdio.h> #define ROW 5 #define COL 5 // 方向数组，用于上下左右移动 const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, 1, 0, -1}; // 判断坐标是否合法 int isValid(int x, int y) { return (x >= 0 && x < ROW && y >= 0 && y < COL); } // DFS函数 void dfs(char maze[ROW][COL], int visited[ROW][COL], int x, int y) { if (!isValid(x, y) || visited[x][y] || maze[x][y] == '1') { return; } printf("(%d,%d)\n", x, y); // 打印当前节点位置 visited[x][y] = 1; for (int i = 0; i < 4; ++i) { int newX = x + dx[i]; int newY = y + dy[i]; dfs(maze, visited, newX, newY); } } ``` #### 2. 主程序逻辑 初始化迷宫地图，并调用DFS进行探索。 ```c int main() { char maze[ROW][COL] = { {'S', '0', '1', '0', '0'}, {'0', '1', '0', '0', '1'}, {'0', '0', '0', '1', '0'}, {'1', '1', '0', '1', '0'}, {'0', '0', '0', '0', 'E'} }; int visited[ROW][COL] = {0}; // 初始化访问标记 printf("Starting DFS from position S:\n"); for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL; ++j) { if (maze[i][j] == 'S') { dfs(maze, visited, i, j); // 起点为'S' } } } return 0; } ``` 上述代码实现了通过DFS对迷宫进行探索的功能。如果需要找到特定目标（如终点'E'），可以在`dfs`函数中加入判断条件[^1]。 --- #### BFS版本 对于某些场景，可能更倾向于使用BFS来寻找最短路径： ```c #include <stdio.h> #include <stdbool.h> #include <stdlib.h> typedef struct { int x, y; } Node; bool isValid(int x, int y) { return (x >= 0 && x < ROW && y >= 0 && y < COL); } void bfs(char maze[ROW][COL]) { bool visited[ROW][COL] = {false}; Node start = {0, 0}; // 假设起点在(0,0) Node queue[ROW * COL]; // 定义队列 int front = 0, rear = 0; queue[rear++] = start; visited[start.x][start.y] = true; while (front < rear) { Node current = queue[front++]; printf("(%d,%d)\n", current.x, current.y); if (maze[current.x][current.y] == 'E') break; // 如果到达终点，则停止 for (int i = 0; i < 4; ++i) { int newX = current.x + dx[i]; int newY = current.y + dy[i]; if (isValid(newX, newY) && !visited[newX][newY] && maze[newX][newY] != '1') { visited[newX][newY] = true; queue[rear++].x = newX; queue[rear++].y = newY; } } } } ``` 此部分展示了如何利用BFS完成类似的迷宫探索任务[^2]。 --- ### 总结 以上提供了两种主要方式——DFS与BFS——来处理地下迷宫探索问题。具体选择取决于实际需求：如果是寻找所有可达区域，推荐使用DFS；而当关注于最短路径时，建议采用BFS。