廣度優(yōu)先搜索是最簡便的圖的搜索算法之一，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。

深度優(yōu)先是從一個方向一直嘗試下去，直到走不通的時候在回到原來地方繼續(xù)尋找。而廣度優(yōu)先是通過“一層一層”擴展的方法去尋找目標。擴展時每發(fā)現(xiàn)一個點就將這個點加入到隊列中，直到找到目標為止。

例如下面這道題，從起點到達終點需要幾步？

題目.png

最開始從入口（1，1）處，一步之內(nèi)可以到達的點有（1，2）和（2，1），但是終點并不在這兩個點上，那只能通過（1，2）和（2，1）這兩點繼續(xù)往下走，那么兩步之內(nèi)能到達哪些點呢？只有（2，2）和（3，1），為了防止一個點多次被走到，這里需要一個數(shù)組來記錄一個點是否已經(jīng)走過。

此時兩步到達的點事（2，2）和（3，1），可惜終點并不是這兩點，所以還要繼續(xù)往下走，三步能到的點是（2，3）、（3，2）和（4，1），依舊不是終點，所以需要重復(fù)剛才的方法，直到找終點為止。
完整代碼如下：

#include <stdio.h>

struct note {
    int x;  //橫坐標
    int y;  //縱坐標
    int s;  //步數(shù)
};

int main(int argc, const char * argv[]) {
    
    struct note que[17];    //應(yīng)為地圖大小不超過 4X4，因此隊列擴展不會超過16個
    
    // 記錄走過的點，和標記
    int a[5][5] = {0},mark[5][5]= {0};
    
    // 定義一個用于表示走的方向的數(shù)組
    int next[4][2] = {{0,1}, // 向右走
                      {1,0}, // 下
                      {0,-1},// 左
                      {-1,0} // 上
                        };
    
    int head,tail;
    int k,tx,ty,flag;
    
    //隊列初始化
    head = 1;
    tail = 1;
    //往隊列插入迷宮入口坐標
    que[tail].x = 1;
    que[tail].y = 1;
    que[tail].s = 0;
    tail++;
    mark[1][1] = 1; //起點已經(jīng)走過
    
    // 用來標記是否到達目標點，0表示暫時還沒有到達，1表示到達
    flag = 0;
    // 當隊列不為空的時候循環(huán)
    while (head < tail) {
        // 枚舉4個方向
        for (k = 0; k <= 3; k++) {
            
            // 計算下一個點的坐標
            tx = que[tail].x + next[k][0];
            ty = que[tail].y + next[k][1];
            
            // 判斷是否越界
            if (tx <1 || tx >5 || ty <1 || ty >4) continue;
            // 判斷是否是障礙物或者已經(jīng)在路徑中
            if (a[tx][ty] == 0 && mark[tx][ty] == 0) {
                
                // 把這個點標記為已經(jīng)走過，每個點只入隊一次
                mark[tx][ty] = 1;
                // 插入新的點到隊列中
                que[tail].x = tx;
                que[tail].y = ty;
                que[tail].s = que[head].s +1;   // 步數(shù)加1
                tail++;
                
            }
            
            // 如果找到目標點，停止擴展，任務(wù)結(jié)束，退出循環(huán)
            if (tx == 4 && ty == 3) {
                flag = 1;
                break;
            }
        }
        if (flag == 1) {
            break;
        }
        // 當一個點擴展結(jié)束后，head++才能對后面的點再進行擴展
        head++;
    }
    // tail是指向隊列隊尾的下一個位置，所以需要-1
    printf("%d",que[tail -1].s);
    
    getchar();getchar();
    return 0;
}