设计程序走出图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 k0; 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 所有进入队列的位置信息位置步数顺序号位置步数顺序号位置步数顺序号(0, 0)11(1,7)99(4,6)1317(0,1)22(2,7)1010(1,5)1318(0,2)33(3,7)1111(6,7)1419(0,3)44(2,6)1112(5,6)1420(0,4)55(4,7)1213(2,5)1421(0,5)66(3,6)1214(7,7)1522(0,6)77(1,6)1215(6,6)1523(0,7)88(5,7)1316(3,5)1524对于表1从整体来看位置信息按照步数由小到大的顺序从队首排到对尾从局部来看步数相同的位置信息在队列中是相邻的从而保证了能找到最短路径也验证了BFS算法的正确性。