采用BFS方法设计程序走出迷宫

设计程序走出图1的迷宫，起点为左上角，终点为右下角。

图1 迷宫图

从左上角到右下角有多条路径，采用BFS方法能获得最短路径。

BFS方法概述：把起始位置加入队列后，边探测所有可达、不越界且首次出现的下一个位置，把它们都加入队列，且在这些位置处记录上一位置；边从队首取出位置，这样的操作不断进行，当从队列中取出的位置是终点时，由终点能倒推到起始点，这就是最短路径。当把队列中的位置都取出而没有终点时，没有可达路径。

核心思想：距离起始点越近的位置越先被探测到，越放在队列的前面，从而保证找到的路径是最短路径。

程序实现方案：

采用结构体数据类型存放位置信息和步数。从队首取出位置结构体时，以位置信息索引，把步数保存到二维数组A，表示到达该位置的步数，它可能是最短路径上的一个位置。把一个位置放入队列时，用二维数组B把它标记为1，防止重复入队列，且以该位置做索引把前一位置记录到二维数组B和C中，用于后续还原路径。

找到最短路径后，从当前位置（终点）依次回溯到起点：从终点开始，以及二维数组B和C中记录的路径位置做索引，把路径步数记录到二维数组D中。从步数为1的位置开始按照步数递增顺序把二维数组D中所有的位置输出，得到最短路径的位置图。输出二维数组D，得到最短路径的步数图。输出二维数组A，得到从起点到达这些位置的步数分布图。

#include <stdio.h> #include <stdlib.h> #define MAX_Q_SIZE 100 // 迷宫地图 int maze[8][8] = { {12, 12, 12, 12, 12, 12, 12, 6}, {10, 12, 14, 12, 4, 10, 6, 3}, {9, 6, 11, 12, 4, 3, 9, 7}, {2, 3, 11, 12, 4, 3, 10, 7}, {11, 5, 9, 12, 6, 3, 3, 3}, {3, 10, 12, 6, 3, 3, 3, 3}, {3, 3, 10, 5, 9, 5, 3, 3}, {9, 5, 9, 12, 12, 12, 13, 13} }; // 行号列号变化率数组, 方向顺序：下、右、上、左 int drdc[2][4] = { {1, 0, -1, 0}, {0, 1, 0, -1} }; // --- 位置结构节点 --- typedef struct { int r; // 行坐标 int c; // 列坐标 int steps; // 到达该点的步数 } Node; // 队列实现 Node queue[MAX_Q_SIZE]; int front = 0, rear = 0; // --- 辅助数组 --- int visited[8][8] = {0}; // 标记是否访问过 int route[8][8] = {0}; // 记录位置步数 // 记录到达 (r,c) 的前一个位置，用于回溯路径 int parent_r[8][8]; int parent_c[8][8]; void enqueue(Node n); Node* dequeue(); int isQueueEmpty(); int canMove(int r, int c, int direction); int BFS_maze(); void route_location(); void path_steps(int rc[8][8], int ); void route_steps(); void maze_steps(); void remain_steps(Node *); void site_queue(Node *); int main() { Node *curr1; Node startNode = {0, 0, 1}; // 起点 (0,0)，步数为1 enqueue(startNode); //加入队列 visited[0][0] = 1; // --- 输出结果 --- if (BFS_maze()) { printf("找到最短路径 (共 %d 步): \n", route[7][7]); route_location(); route_steps(); maze_steps(); printf("\n队列中剩余的位置:\n"); remain_steps(curr1); site_queue(curr1); } else { printf("没有找到路径！\n"); } getchar(); return 0; } void enqueue(Node n) // 加入队列 { if (rear < MAX_Q_SIZE) queue[rear++] = n; } Node* dequeue() // 获得队首格子结构的地址后移出队列 { if (front < rear) return &queue[front++]; return NULL; } int isQueueEmpty() // 空队列 { return front == rear; } // 判断能否移动 int canMove(int r, int c, int direction) { int cell = maze[r][c]; if (direction == 0 && (cell & 2)) return 1; // 0=下, 2=能下移 if (direction == 1 && (cell & 8)) return 1; // 1=右, 8=能右移 if (direction == 2 && (cell & 1)) return 1; // 2=上, 1=能上移 if (direction == 3 && (cell & 4)) return 1; // 3=左, 4=能左移 return 0; } int BFS_maze() // 找最短路径 { int pathFound = 0; while (!isQueueEmpty()) { Node* curr = dequeue(); int currR = curr->r; int currC = curr->c; int currSteps = curr->steps; // 记录到达当前点的步数 route[currR][currC] = currSteps; // 如果到达终点 (7, 7) if (currR == 7 && currC == 7) { pathFound = 1; break; // BFS 首次到达终点即为最短路径 } // 尝试四个方向 for (int i = 0; i < 4; i++) { int nr = currR + drdc[0][i]; int nc = currC + drdc[1][i]; // 检查边界、是否可移动、是否访问过 if (nr >= 0 && nr < 8 && nc >= 0 && nc < 8 && canMove(currR, currC, i) && !visited[nr][nc] ) { // 记录父节点，用于后续还原路径 parent_r[nr][nc] = currR; parent_c[nr][nc] = currC; Node nextNode = {nr, nc, currSteps + 1}; enqueue(nextNode); visited[nr][nc] = 1; // 做标记，防止重复入队 } } } return pathFound; } void route_location() // 打印路径位置图 { int path_rc[8][8] = { 0 }; // 路径位置索引步数 int cnt1 = route[7][7]; // 记录终点步数 path_steps(path_rc, cnt1); // 输出路径 for(int num = 1; num <= cnt1; num++) { int found = 0; for (int r = 0; r < 8; r++) { for(int c = 0; c < 8; c++) if( path_rc[r][c]== num ) { found = 1; printf("(%d, %d) ", r, c); if (num % 8 == 0) printf("\n"); break; } if(found == 1) { found = 0; break; } } } printf("\n"); } void path_steps(int rc[8][8], int cnt) // 路径位置记录步数 { int tr = 7, tc = 7; while(cnt) { int temp_r, temp_c; rc[tr][tc] = cnt--; temp_r = parent_r[tr][tc]; temp_c = parent_c[tr][tc]; tr = temp_r; tc = temp_c; } } void route_steps() // 打印路径步数图 { int path_rc[8][8] = { 0 }; // 路径位置索引步数 int cnt1 = route[7][7]; // 记录终点步数 path_steps(path_rc, cnt1); printf("\n路径步数分布图:\n"); for(int i = 0; i < 8; i++) { for(int j = 0; j < 8; j++) { if(path_rc[i][j] < 10 ) printf(" %d ", path_rc[i][j]); else printf("%d ", path_rc[i][j]); } printf("\n"); } } void maze_steps() // 打印地图上的步数分布 { printf("\n迷宫位置步数分布图:\n"); for(int i = 0; i < 8; i++) { for(int j = 0; j < 8; j++) { if(route[i][j] < 10 ) printf(" %d ", route[i][j]); else printf("%d ", route[i][j]); } printf("\n"); } } void remain_steps(Node *cur) // 打印队列中剩余的位置信息 { while( !isQueueEmpty() ) { cur = dequeue(); printf("位置:(%d, %d) 步数:%d ", cur->r, cur->c, cur->steps); } } void site_queue(Node *cur) // // 打印所有进入队列的位置信息 { int k=0; front = 0; while( !isQueueEmpty() ) { cur = dequeue(); printf("\n(%d, %d) :%d ", cur->r, cur->c, cur->steps); k++; } printf("\n%d", k); }

找到最短路径 (共 15 步):
(0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) (0, 6) (0, 7)
(1, 7) (2, 7) (3, 7) (4, 7) (5, 7) (6, 7) (7, 7)

路径步数分布图:

图2 路径步数分布图（从1逐渐递增到15）

迷宫位置步数分布图:

图3 迷宫位置步数分布图

队列中剩余的位置:
位置:(6, 6) 步数:15 位置:(3, 5) 步数:15

图3中有一些步数是相同值，表明从起点到达这些位置的步数相等。（7, 7）、(6, 6) 和(3, 5) 步数都是15，因为（7, 7）的信息先于(6, 6) 和(3, 5) 的信息进入队列，所以（7, 7）的信息先从队列取出，经程序判断是终点，停止从队列中取信息，(6, 6) 和(3, 5)就保留在队列中。

对于表1，从整体来看，位置信息按照步数由小到大的顺序从队首排到对尾，从局部来看，步数相同的位置信息在队列中是相邻的，从而保证了能找到最短路径，也验证了BFS算法的正确性。