BFS(宽度优先搜索)
简介
宽度优先搜索(BFS,breadth-First Search)也是一种搜索的手段。是从一个状态开始,总是先搜索离它最近的所有状态,所以对于宽度优先搜索,同一个状态只经过一次,复杂度为O(状态数*转移的方式)
BFS的基本思路
它是按照开始状态——>只需一次就可以到达的所有状态——>只需二次转移就可以到达的所有状态——>····
从数据结构上来看DFS利用了栈,而BFS则利用的队列。搜索时首先将初始状态添加到队列里,然后又不断地从队头取出状态,把从该状态可以转移到的状态中未被访问过的部分加入队列,如此往复,直到队列被取空或找到问题的解。
模板——https://www.acwing.com/problem/content/849/
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. 走迷宫 https://www.acwing.com/activity/content/problem/content/907/
#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即可;