跳转至

BFS

前置知识

队列，queue

目标

具体状态的BFS，比如棋盘上的遍历问题，flood fill

What

breadth first search(bfs) 宽度优先搜索。算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。

这块应该先去了解一下图上的遍历的过程，更好理解代码。

主要场景：棋盘问题（就是在一个矩阵上遍历），Flood Fill，问题状态的表述升级，最短路 / 最少步数 / 最少次数，就是图论最短路问题，边权是 1 的情况。

How

img

【例8.2】细胞

题意，一个矩阵由0~9组成，非零部分为细胞，求有多少个细胞

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e4 + 10;

char s[N][N];
int n, m; 

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

void bfs(int ux, int uy)
{
    queue<PII> q;
    q.push({ux, uy});

    while (!q.empty()){
        PII t = q.front(); q.pop();
        int x = t.first, y = t.second;
        s[x][y] = '0';

        for (int i = 0; i < 4; i++){
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (s[a][b] == '0') continue;

            q.push({a, b});
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) scanf("%s", s[i]);

    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++){
            if (s[i][j] != '0'){
                bfs(i, j);
                cnt++;
            }
        }

    cout << cnt << '\n';

    return 0;
}

1251：仙岛求药

#include <bits/stdc++.h>

using namespace std;

char g[25][25];
int d[25][25], x, y;
int m, n, dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int bfs() {
    memset(d, -1 , sizeof(d));

    queue <pair<int, int> > q;
    q.push({x, y});
    d[x][y] = 0;

    while(!q.empty()) {
        pair<int, int> t = q.front(); q.pop();
        for(int i = 0;i < 4;i++){
            int ux = t.first + dx[i], uy = t.second + dy[i];
            if(ux < 0 || ux >= n || uy < 0 || uy >= m) continue;    
            if(g[ux][uy] == '#' || d[ux][uy] != -1) continue;

            d[ux][uy] = d[t.first][t.second] + 1;
            q.push({ux, uy});

            if(g[ux][uy] == '*') return d[ux][uy];
        }
    }

    return -1;
}

int main() {
    while(cin >> n >> m) {
        if(n == 0 && m == 0) break; 
        for(int i = 0;i < n;i++) cin >> g[i];

        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                if(g[i][j] == '@') {
                    x = i;
                    y = j;
                }
            }
        }

        cout << bfs() << endl;
    }

    return 0;
}

题单

总结

BFS的代码模板，是比较固定的，就是使用queue，熟练了之后，这些题目可以较快的刷完。

如果有难度的地方，就是二维迷宫，比较好表示。三位迷宫，可能会麻烦一点，道理是一样的。

细节的地方，入队的时候，有时需要判断是否重复入队，这经常会引发RE（队列也会炸）。

BFS也是进阶图论的是个入口，求最短路的一个做法。