广度优先搜索(Breadth First Search)

BFS 又称宽搜。与 DFS 一条路走到黑不同，BFS 可以看作是警察地毯式的搜山。宽搜的搜索顺序可以通过搜索树来理解。

深搜依赖的是递归算法，而宽搜依赖的则是一种数据结构——队列。

BFS 算法模板

void bfs() {
    // 队列初始化，起点入队
    while(hh <= tt) {   // 队列非空
        auto h = q[h++];     // 取队头，队头出队
        for(可以扩展到的结点v && 该结点未被访问) {
            q[++t] = v; // 结点入队
            if(结点v是目标结点) {
                输出结果
                return ;
            }
        }
    }
}

经典宽搜问题

跳马迷宫问题

走迷宫

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int g[N][N], d[N][N], n, m;

typedef pair<int, int> PII;
PII q[N * N];

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

int bfs() {
    int hh = 0, tt = 0;
    q[0] = {0, 0};

    memset(d, -1, sizeof d);
    d[0][0] = 0;

    while(hh <= tt) {
        auto h = q[hh++];

        for(int i = 0; i < 4; i++) {
            int x = h.first + dx[i];
            int y = h.second + dy[i];

            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
                d[x][y] = d[h.first][h.second] + 1;
                q[++tt] = {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;
}

迷宫问题

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1010;

int g[N][N];
PII q[N * N], pre[N][N];

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

void bfs(int x, int y) {
    memset(pre, -1, sizeof pre);

    int hh = 0, tt = 0;
    q[0] = {x, y};

    while(hh <= tt) {
        PII t = q[hh++];
        for(int i = 0; i < 4; i++) {
            int a = t.first + dx[i];
            int b = t.second + dy[i];
            if(a >= 0 && a < n && b >= 0 && b < n && g[a][b] == 0 && pre[a][b].first == -1) {
                q[++tt] = {a, b};
                pre[a][b] = t;
            }
        }
    }
}

int main() {
    cin >> n;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }

    bfs(n - 1, n - 1);

    PII end(0, 0);

    while(true) {
        cout << end.first << " " << end.second << endl;
        if(end.first == n - 1 && end.second == n - 1) break;
        end = pre[end.first][end.second];
    }

    return 0;
}

Flood Fill问题

池塘计数

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 1010;
const int M = N * N;

int n, m;
char g[N][N];
PII q[M];

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

void bfs(int x, int y) {
    int hh = 0, tt = 0;
    q[0] = {x, y};
    g[x][y] = '.';

    while(hh <= tt) {
        PII t = q[hh++];

        for(int i = 0; i < 8; i++) {
            int a = t.first + dx[i], b = t.second + dy[i];
            if(a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 'W') {
                g[a][b] = '.';
                q[++tt] = {a, b};
            }
        }
    }
}

int main() {
    cin >> n >> m;

    for(int i = 0; i < n; i++) {
        cin >> g[i];
    }

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

    cout << cnt << endl;

    return 0;
}

思考题：AcWing 173. 矩阵距离