# Ch19 BFS 廣度優先搜尋
> 搭配 [virtual judge解題系統](https://vjudge.net/contest/273370)
##
> 上一章:[stack與queue](https://hackmd.io/s/BkZaF56Cm)
> 下一章:[最短路徑 Dijkstra](https://hackmd.io/s/HJL8bMuxN)
> 回目錄:[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)
## <font color='darkblue'>什麼是搜尋</font>
![](https://i.imgur.com/8wor4Tp.png)
首先來看看這張圖
藍色是起點,紅色是終點
黑色的格子不能走,也不能走出大方塊外
請問從藍色走到紅色最少需要幾步呢?
![](https://i.imgur.com/dD7OcwP.png)
用人眼睛判斷的話
很容易就能夠看出來灰色是最近的一條路
並且知道要走13格能抵達
那麼我們要怎麼寫程式來找出答案呢
就是這章要學習的「搜尋演算法」
## <font color='darkblue'>廣度優先搜尋</font>
想要從藍色走到紅色
可以隨便亂走,邊走邊紀錄走了幾步
然而走到紅色時,你卻無法確保這是最快的走法
那麼怎麼樣能確定走的是最快的走法呢?
我們以藍色為中心向外擴散
把距離為1的格子都標示出來
再從那些被標上1的格子開始,把距離為2的格子都標示出來
...
一直標到紅色格子,就可以確保是最少步了
![](https://i.imgur.com/DM1IMGp.gif)
依照這種順序來拜訪格子們
就稱為「廣度優先搜尋」
## <font color='darkblue'>寫廣度優先搜尋的程式</font>
首先,我們先記得現在站的起點是藍色格子
也就是(3, 1)的座標
```cpp=
int row=3;
int col=1;
```
再要先把藍色的格子標上「0步」
代表從藍色格子走到藍色格子只需要花0步
```cpp=3
step[row][col]=0;
```
接下來我們要把目前位置的上下左右都標上1
代表從藍色走到這些格子需要1步
```cpp=4
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;
```
這樣寫有點太累了
乾脆寫成這樣
```cpp=
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這格還沒被拜訪過)
因此上面的程式應該改成
```cpp=4
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;
}
```
![](https://i.imgur.com/U3bC8I6.png)
好了,現在標完1
接著要標2
我們要從所有被標上1的格子為中心點,標它的上下左右
然而,我們要怎麼有效率地找出所有被標上1的格子呢?
我們可以在把這些格子標上數字的時候
順便把這些格子都放進一個「袋子」記錄起來
接著每次都從這袋子取出一個格子來當中心點,來標它的上下左右
由於我們希望每次從袋子裡取出的都是距離起點最近的格子
也就是最舊、最早放進去的格子
該怎麼做呢?
## <font color='darkblue'>廣度優先搜尋的好夥伴:Queue</font>
答案是使用上一章提到的Queue!!!
首先宣告一個queue
裡面要可以放「pair<int, int>」
因為表達格子座標需要兩個數字
```cpp=
queue< pair<int, int> > q;
```
接下來我們重新做一次剛才示範過的「標格子」
並且配上queue的使用
首先,先將起點標上「0」步
並且將起點放進queue裡
```cpp=
int row=3;
int col=1;
step[row][col]=0;
pair<int, int> start = make_pair(row, col);
q.push(start);
```
接下來就是不斷從queue裡面抓出一個格子
```cpp=
while(!q.empty()){
pair<int, int> cur = q.front();
q.pop();
int row=cur.first;
int col=cur.second;
}
```
抓出一個格子之後
先判斷他是不是我們要的紅格子
如果是的話
就代表我們找到答案了
```cpp=
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裡
```cpp=
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);
}
}
```
最後需要檢查的是如果整個袋子都抽完了
就代表藍色根本走不到紅色
```cpp=
bool found = 0;
while(!q.empty())
{
//blablabla
if(找到紅色){
found = 1;
cout<<blabla
break;
}
//blablabla
}
if(found==0) cout<<"Impossible"<<endl;
```
這樣一來就完成啦!!
最後要記得補上的是每次做之前要先把step陣列的每一格都設成-1
以及要把queue清空
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [C - Crazy King ](https://vjudge.net/contest/273370#problem/B)
>
> 國王想從A走到B
> 然而路上有許多馬,標示為Z
> 國王不能走到有馬個格子上
> 也不能走到馬可以走一個馬步就走到的格子上
> 因為馬會把國王吃掉
> 請問國王最少要走幾步才能從A走到B?
> 若走不到,也請印出走不到
這題可以把所有馬走得到的位置都先標成X
表示國王不能走到Z也不能走到X
再像範例一樣做就好
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [A - Dungeon Master](https://vjudge.net/contest/273370#problem/A)
>
> 你在一個3D的世界裡
> 起點為S,終點為E
> 有些格子被堵住了
> 請問從S走到E最少需要幾步呢?
> 如果無法從S走到E,也請印出"Trapped!"
>
> 首先會輸入L、R、C代表這個世界的高、長、寬
> 接下來會輸入L個二維陣列,其大小為R\*C
> 其中陣列中的.代表能走的格子
> #代表不能走的格子
像範例一樣的題目
但是因為有三維
所以可以寫成
```cpp=
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};
```
<font color="darkgreen"> 【學生練習題】</font>
> - [ ] [B - Knight Moves ](https://vjudge.net/contest/273370#problem/B)
>
> 騎士只能走馬步
> 請問走著這種馬步,最少要幾步才能從起點走到終點呢?
> 給予兩個座標代表起點和終點
> 請算出最少要幾步才能從起點走到終點
> 沒有障礙物,保證一定走得到
> 但要記得一定是馬步喔!
騎士只能走馬步,馬步有八種
```cpp=
int dx[8]={1, 1, -1, -1, 2, 2, -2, -2};
int dy[8]={2, -2, 2, -2, 1, -1, 1, -1};
```
##
> 上一章:[stack與queue](https://hackmd.io/s/BkZaF56Cm)
> 下一章:[最短路徑 Dijkstra](https://hackmd.io/s/HJL8bMuxN)
> 回目錄:[國立科學園區實驗中學C++程式語言自學講義](https://hackmd.io/s/B18yT_i5Z)