广度优先搜索

广度优先搜索碰到岔路口时，总是依次访问该路口可直接到达的所有岔路，直至遇到新的岔路口，并记下这些岔路口。下一次从新的岔路口依次重复原来的操作。广度优先搜索适合用队列实现，一个元素出队，将该元素可直接到达的所有元素依次放入队尾。

1. 求解迷宫问题

#include <stdio.h>
#define MaxSize 500

// 建立队列
struct SqQueue{
    int i, j;
    int pre;
}qu[MaxSize];
int front = -1, rear = -1;

void print(int front);

int main()
{
    // 建立迷宫
    int mg[10][10]={
        {1,1,1,1,1,1,1,1,1,1},
        {1,0,0,1,0,0,0,1,0,1},    
        {1,0,0,1,0,0,0,1,0,1},
        {1,0,0,0,0,1,1,0,0,1},
        {1,0,1,1,1,0,0,0,0,1},
        {1,0,0,0,1,0,0,0,0,1},
        {1,0,1,0,0,0,1,0,0,1},
        {1,0,1,1,1,0,1,1,0,1},
        {1,1,0,0,0,0,0,0,0,1},
        {1,1,1,1,1,1,1,1,1,1}
    };

    // 标记起点和终点
    int si, sj, ei, ej;
    si = sj = 1;
    ei = ej = 8;

    // 在队列中放入起始点
    int i, j, di;
    rear++;
    qu[rear].i = si; qu[rear].j = sj; qu[rear].pre = -1;
    mg[si][sj] = -1;

    while(front!=rear){
        front++;
        i = qu[front].i; j = qu[front].j;
        if(i==ei && j==ej){
            print(front);
            return 1;
        }
        for(di=0; di<4; di++){
            // 将可能的状态入队
            switch(di){
                case 0: i = qu[front].i; j = qu[front].j+1; break;
                case 1: i = qu[front].i+1; j = qu[front].j; break;
                case 2: i = qu[front].i; j = qu[front].j-1; break;
                case 3: i = qu[front].i-1; j = qu[front].j; break;
            }
            if(mg[i][j]==0){
                rear++;
                qu[rear].i = i; qu[rear].j = j; qu[rear].pre = front;
                mg[i][j] = -1;
            }
        }
    }
    printf("There is no path!\n");
    return 0;
}

void print(int front)
{
     int k = front, j;
     do{
         j = k;
         k = qu[k].pre;
         qu[j].pre = -1;
     }while(k!=0);
     printf("Find the path that:\n");
     k = 0;
     int ns = 0;
     while(k<=front){
         if(qu[k].pre==-1){
             ns++;
            printf("\t(%d, %d)", qu[k].i, qu[k].j);
            if(ns%5==0)
                printf("\n");
         }
        k++; 
     }
 }