# 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)