Ch19 BFS 廣度優先搜尋

搭配 virtual judge解題系統

上一章：stack與queue
下一章：最短路徑 Dijkstra
回目錄：國立科學園區實驗中學C++程式語言自學講義

什麼是搜尋

首先來看看這張圖
藍色是起點，紅色是終點
黑色的格子不能走，也不能走出大方塊外
請問從藍色走到紅色最少需要幾步呢?

用人眼睛判斷的話
很容易就能夠看出來灰色是最近的一條路
並且知道要走13格能抵達

那麼我們要怎麼寫程式來找出答案呢
就是這章要學習的「搜尋演算法」

廣度優先搜尋

想要從藍色走到紅色
可以隨便亂走，邊走邊紀錄走了幾步
然而走到紅色時，你卻無法確保這是最快的走法

那麼怎麼樣能確定走的是最快的走法呢?

我們以藍色為中心向外擴散
把距離為1的格子都標示出來
再從那些被標上1的格子開始，把距離為2的格子都標示出來
…
一直標到紅色格子，就可以確保是最少步了

依照這種順序來拜訪格子們
就稱為「廣度優先搜尋」

寫廣度優先搜尋的程式

首先，我們先記得現在站的起點是藍色格子
也就是(3, 1)的座標

int row=3;
int col=1;

再要先把藍色的格子標上「0步」
代表從藍色格子走到藍色格子只需要花0步

step[row][col]=0;

接下來我們要把目前位置的上下左右都標上1
代表從藍色走到這些格子需要1步

step[row][col+1] = step[row][col]+1;
step[row][col-1] = step[row][col]+1;
step[row+1][col] = step[row][col]+1;
step[row-1][col] = step[row][col]+1;

這樣寫有點太累了
乾脆寫成這樣

int dx[4]={0, 0, 1, -1};
int dy[4]={1, -1, 0, 0};
for(int i=0;i<4;i++){
    int new_row=row+dx[i];
    int new_col=col+dy[i];
    step[new_row][new_col]=step[row][col]+1;
}

然而在標上1之前
其實有許多事情要先檢查

1. 這格是不是超出大方塊外了?
2. 這格是不是黑格子? (假設world[x][y]=='X'代表x,y這格是黑格子)
3. 這格是不是之前標過號碼了? (假設step[x][y]==-1代表x,y這格還沒被拜訪過)

因此上面的程式應該改成

for(int i=0;i<4;i++){
    int new_row=row+dx[i];
    int new_col=col+dy[i];
    if(new_row<0||new_row>=6||new_col<0||new_col>=6) continue;
    if(world[new_row][new_col]=='X') continue;
    if(step[new_row][new_col]!=-1) continue;
    step[new_row][new_col]=step[row][col]+1;
}

好了，現在標完1
接著要標2
我們要從所有被標上1的格子為中心點，標它的上下左右

然而，我們要怎麼有效率地找出所有被標上1的格子呢?

我們可以在把這些格子標上數字的時候
順便把這些格子都放進一個「袋子」記錄起來
接著每次都從這袋子取出一個格子來當中心點，來標它的上下左右

由於我們希望每次從袋子裡取出的都是距離起點最近的格子
也就是最舊、最早放進去的格子
該怎麼做呢?

廣度優先搜尋的好夥伴：Queue

答案是使用上一章提到的Queue!!!

首先宣告一個queue
裡面要可以放「pair<int, int>」
因為表達格子座標需要兩個數字

queue< pair<int, int> > q;

接下來我們重新做一次剛才示範過的「標格子」
並且配上queue的使用

首先，先將起點標上「0」步
並且將起點放進queue裡

int row=3;
int col=1;
step[row][col]=0;
pair<int, int> start = make_pair(row, col);
q.push(start);

接下來就是不斷從queue裡面抓出一個格子

while(!q.empty()){
    pair<int, int> cur = q.front();
    q.pop();
    int row=cur.first;
    int col=cur.second;
}

抓出一個格子之後
先判斷他是不是我們要的紅格子
如果是的話
就代表我們找到答案了

while(!q.empty()){
    pair<int, int> cur = q.front();
    q.pop();
    int row=cur.first;
    int col=cur.second;
    if(row==red_row&&col==red_col){
        cout<<step[row][col]<<endl;
        break;
    }
}

否則的話
我們要從這個點為中心出發
找出它上下左右的格子
標出步數並且放進queue裡

while(!q.empty()){
    pair<int, int> cur = q.front();
    q.pop();
    int row=cur.first;
    int col=cur.second;
    if(row==red_row&&col==red_col){
        cout<<step[row][col]<<endl;
        break;
    }
    for(int i=0;i<4;i++){
        int new_row=row+dx[i];
        int new_col=col+dy[i];
        if(new_row<0||new_row>=N||new_col<0||new_col>=N) continue;
        if(world[new_row][new_col]=='X') continue;
        if(step[new_row][new_col]!=-1) continue;
        step[new_row][new_col]=step[row][col]+1;
        pair<int, int> next=make_pair(new_row, new_col);
        q.push(next);
    }
}

最後需要檢查的是如果整個袋子都抽完了
就代表藍色根本走不到紅色

bool found = 0;
while(!q.empty())
{
    //blablabla
    if(找到紅色){
        found = 1;
        cout<<blabla
        break;
    }
    //blablabla
}
if(found==0) cout<<"Impossible"<<endl;

這樣一來就完成啦!!
最後要記得補上的是每次做之前要先把step陣列的每一格都設成-1
以及要把queue清空

【學生練習題】

• C - Crazy King

國王想從A走到B
然而路上有許多馬，標示為Z
國王不能走到有馬個格子上
也不能走到馬可以走一個馬步就走到的格子上
因為馬會把國王吃掉
請問國王最少要走幾步才能從A走到B?
若走不到，也請印出走不到

這題可以把所有馬走得到的位置都先標成X
表示國王不能走到Z也不能走到X
再像範例一樣做就好

【學生練習題】

• A - Dungeon Master

你在一個3D的世界裡
起點為S，終點為E
有些格子被堵住了
請問從S走到E最少需要幾步呢?
如果無法從S走到E，也請印出"Trapped!"

首先會輸入L、R、C代表這個世界的高、長、寬
接下來會輸入L個二維陣列，其大小為R*C
其中陣列中的.代表能走的格子
#代表不能走的格子

像範例一樣的題目
但是因為有三維
所以可以寫成

int dx[6]={0,0,0,0,1,-1};
int dy[6]={1,-1,0,0,0,0};
int dz[6]={0,0,1,-1,0,0};

【學生練習題】

• B - Knight Moves

騎士只能走馬步
請問走著這種馬步，最少要幾步才能從起點走到終點呢?
給予兩個座標代表起點和終點
請算出最少要幾步才能從起點走到終點
沒有障礙物，保證一定走得到
但要記得一定是馬步喔!

騎士只能走馬步，馬步有八種

int dx[8]={1, 1, -1, -1, 2, 2, -2, -2};
int dy[8]={2, -2, 2, -2, 1, -1, 1, -1};

上一章：stack與queue
下一章：最短路徑 Dijkstra
回目錄：國立科學園區實驗中學C++程式語言自學講義