宽度优先搜索(BFS,breadth-First Search)也是一种搜索的手段。是从一个状态开始,总是先搜索离它最近的所有状态,所以对于宽度优先搜索,同一个状态只经过一次,复杂度为O(状态数*转移的方式)
它是按照开始状态——>只需一次就可以到达的所有状态——>只需二次转移就可以到达的所有状态——>····
从数据结构上来看DFS利用了栈,而BFS则利用的队列。搜索时首先将初始状态添加到队列里,然后又不断地从队头取出状态,把从该状态可以转移到的状态中未被访问过的部分加入队列,如此往复,直到队列被取空或找到问题的解。
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]; } } }
#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方向上的符合条件的移动,如果没走过这个点就将这个点放入队列d[x][y]就相应的加上1,如此反复,直到搜索到最快的路径
return即可;