搜索算法——BFS

广度优先搜索算法

是最简便的图的搜索算法之一，又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
BFS以广度作为状态转移依据，BFS会优先访问本层的所以结点，然后进入下一层
我们使用队列来实现此算法
1.将起点加入队列
2.从队首取出一个结点
3.扫描这个结点能到的所有未被访问的结点，将他们入队
4.重复步骤2和3，直到队列为空，结束
以上图为例讲解算法流程：
首先将1入队，将1出队，扫描1能到的未被访问的结点2，6，将2，6入队，将2取出，扫描2能到达的结点3和4，再取出6，扫描6能到达的结点，依次类推直至队列为空
还是这个例题

思路：
（1）将初始节点入队，计数+1
（2）将队首节点出队并进入该节点。
（3）以上下左右的顺序寻找未被访问过的黑色节点，将它们入队，计数+1并打上标记，代表这个节点已经被统计过了。
（4）重复（2）（3）直至队列空。
代码如下：

int a[25][25];
int dx[4] = {
     -1,0,1,0 };
int dy[4] = {
     0,1,0,-1 };//下一步可以怎么走
int qx[20 * 20 + 10];
int qy[20 * 20 + 10];
void bfs(int sx, int sy)
{
    a[sx][sy] = 1;//打标记int h = 0; int t = 1;qx[h] = sx; qy[h] == sy;//初始结点入队while (h < t){
    int x = qx[h];int y = qy[h];h++;//队首出队for (int i = 0; i < 4; i++){
    int nx = x + dx[i];int ny = y + dy[i];//状态转移if (!a[nx][ny])//如果可以走{
    a[nx][ny] = 1;qx[t] = nx;qy[t] = ny;//入队t++;}}}return;
}

看一个例题洛谷p1135

算法：BFS
思路：
我们把此电梯问题看作是一张图，从一个楼层到另一个楼层看作一条路，此题便可以转化成搜索一张图，求最短路，注意一点，如果起点和目的地一样的话，直接输出0
代码：

#include<iostream>
#include<cstdio>
using namespace std;
int a, b;
int n;
int q[201];
int dep[201];
int vis[201];
int ans = 0;
int num[205];
void bfs(int s)
{
    int h = 0, t = 1;q[h] = s;dep[h] = 0;vis[s] = 1;while (h < t){
    int now = q[h];h++;if (now == b){
    ans = dep[h - 1];break;}if (now + num[now] <= n && !vis[now + num[now]]){
    dep[t] = dep[h - 1] + 1;q[t++] = now + num[now];vis[now + num[now]] = 1;}if (now - num[now]  >=1 && !vis[now - num[now]]){
    dep[t] = dep[h - 1] + 1;q[t++] = now - num[now];vis[now - num[now]] = 1;}}
}
int main()
{
    cin >> n >> a >> b;for (int i = 1; i <= n; i++){
    cin >> num[i];}bfs(a);if (a == b)cout << 0;else if (ans == 0){
    cout << -1;}else cout << ans;return 0;
}