算法思想

广度优先搜索算法的基本思想是：从初始状态S开始，利用规则，生成下一步可能的状态。构成树的下一层节点，检查是否出现出口G，若未出现，就对该层所有状态节点，分别顺序利用规则。生成再下一层的所有状态节点，直到出现目标状态为止。

程序实现

  1. 定义结构体和相关数组
  1. int head, rear, size = 0, num = 0;
  2. typedef struct node {
  3.     int x, y;
  4.     struct node *next;
  5. } node_t;
  7. node_t b[N], way[N]; //队列b，和记录路径坐标的结构体数组
  9. int a[N][N]; //构造地图
  1. 打印最短路径
  1. void print_path() {
  2.     int i;
  3.     for(i = num - 1 ; i >= 0 ; i--) {
  4.         printf("(%d, %d)\n", way[i].x, way[i].y);
  5.     }
  6. }
  1. 将整个地图周围用1围起来，方便搜索
  1. void surround() {
  2.     int i , j ;
  3.     for(i = 0 ; i< size + 2 ; i++) {
  4.         for(j = 0 ; j < size + 2 ; j++) {
  5.             if(i == 0 || i == size + 1 || j == 0 || j == size + 1) {
  6.                 a[i][j] = 1;
  7.             }
  8.         }
  9.     }
  10. }
  1. 初始化队列
  1. void init() {
  2.     head = 0;
  3.     rear = 0;
  4. }
  1. 弹出队列成员
  1. node_t *pop() {
  2.     node_t *p;
  3.     p = &b[head];
  4.     head++;
  5.     return p;
  6. }
  1. 将走过的点信息加入队列，next为指向上一个节点数据的指针
  1. void record(int x ,int y ,node_t * next) {
  2.     b[rear].x = x;
  3.     b[rear].y = y;
  4.     b[rear].next =next;
  5.     rear++;
  6. }
  1. 遍历地图，查找路径
  1. void travel() {
  2.     node_t *temp;
  3.     record(1, 1, NULL);
  4.     while(1) {
  5.         if(head >= rear) return;//当队头和队尾相等时，退出
  6.         temp = pop();
  7.         //当走到终点时，用way数组又保存返回到起点的路径
  8.         if(temp -> x == size && temp->y == size) {
  9.             //将第一个数据的next指针指向空，作为返回起点的终止条件。
  10.             while(temp != NULL) {
  11.                 way[num].x = temp->x - 1;
  12.                 way[num].y = temp->y - 1;
  13.                 num++;
  14.                 temp = temp->next;
  15.             }
  16.             return;
  17.         }
  18.         //遍历四个方向，只要满足条件，就加入队列
  19.         if(a[temp->x][temp->y - 1] != 1) {
  20.             record(temp->x, temp->y - 1, temp);
  21.             a[temp->x][temp->y - 1] = 1;
  22.         }
  23.         if(a[temp->x][temp->y + 1] != 1) {
  24.             record(temp->x ,temp->y + 1 ,temp);
  25.             a[temp->x][temp->y + 1] = 1;
  26.         }
  27.         if(a[temp->x - 1][temp->y] != 1) {
  28.             record(temp->x - 1 ,temp->y, temp);
  29.             a[temp->x - 1][temp->y] = 1;
  30.         }
  31.         if(a[temp->x + 1][temp->y] != 1) {
  32.             record(temp->x + 1, temp->y, temp);
  33.             a[temp->x + 1][temp->y] = 1;
  34.         }
  35.     }
  36. }
  1. 主函数
  1. int main() {
  2.     printf("请输入一个N*N的迷宫大小N：");
  3.     scanf("%d", &size);
  4.     memset(a, 0, sizeof(a));
  5.     int i, j;
  6.     printf("请输入迷宫内部构造(0表示通路，1表示墙壁)：\n");
  7.     for(i = 1 ; i < size + 1 ; i ++) {
  8.         for(j = 1 ; j < size + 1; j++) {
  9.             if(scanf("%d", &a[i][j]) == EOF) {
  10.                 return 0;
  11.             }
  12.         }
  13.     }
  14.     surround();
  15.     init();
  16.     travel();
  17.     print_path();
  18.     return 0;
  19. }

运行结果

基于队列的BFS迷宫求解算法实现 - 图1