《挑戰程式設計競賽》——BFS

BFS(寬度優先搜尋)

簡介

寬度優先搜尋(BFS，breadth-First Search)也是一種搜尋的手段。是從一個狀态開始，總是先搜尋離它最近的所有狀态，是以對于寬度優先搜尋，同一個狀态隻經過一次，複雜度為O(狀态數*轉移的方式)

BFS的基本思路

它是按照開始狀态——>隻需一次就可以到達的所有狀态——>隻需二次轉移就可以到達的所有狀态——>····

從資料結構上來看DFS利用了棧，而BFS則利用的隊列。搜尋時首先将初始狀态添加到隊列裡，然後又不斷地從隊頭取出狀态，把從該狀态可以轉移到的狀态中未被通路過的部分加入隊列，如此往複，直到隊列被取空或找到問題的解。

模闆——活動 - AcWing

 queue<int> q;
 st[1] = ture; //  表示1号點已經被周遊過了  
 q.push(1); 
 ​
 while(q.size())
 {
     int t = q.front();
     q.pop();
     
     for (int i = h[t];i != -1 ;i = ne[i])
     {
         int j = e[i];
         if (!st[i])
         {
             st[j] = true;
             q.push[j];
         }
     }
 }
           

樣例一 AcWing 844. 走迷宮

 #include <cstring>
 #include <iostream>
 #include <algorithm>
 #include <queue>
 ​
 using namespace std;
 ​
 typedef pair<int,int> PII;
 const int N = 1e5 + 10 ;
 int n,m;
 int g[N][N],d[N][N];
 queue <PII> q;
 ​
 int bfs()
 {
     memset(d,-1,sizeof d);
     d[0][0] = 0;
     q.push({0,0});
 ​
     int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
 ​
     while (q.size())
     {
         auto t = q.front();
         q.pop();
 ​
         for (int i = 0 ; i < 4 ; i ++) 
         {
             int x = t.first + dx[i] ,y = t.second + dy[i];
 ​
             if (x>=0&&x<n&&y>=0&&y<m&&d[x][y]==-1&&g[x][y]==0)
             {
                 d[x][y] = d[t.first][t.second] + 1;
                 q.push({x,y});
             }
         }
     }
     return d[n-1][m-1];
 }
 ​
 int main()
 {
     cin >> n >> m;
     for (int i = 0 ; i < n ; i ++ )
         for (int j = 0 ; j < m ; j ++) 
             cin >> g[i][j];
     
     cout << bfs() <<endl;
     return 0;
 }
           

思路

一般BFS用于求解最短路徑，在此題中我們從最左上角的{0，0}開始搜尋将它放在隊列頭，進行dx，dy方向上的符合條件的移動，如果沒走過這個點就将這個點放入隊列dx就相應的加上1，如此反複，直到搜尋到最快的路徑

return即可；