BFS

BFS算法主要有洪水填充（flood fill）和最短路径两个应用。

一、洪水填充算法（Flood Fill）

例题 1：岛屿个数（第14届省赛真题）

题目描述：

小蓝得到了一副大小为 M × N 的格子地图，可以将其视作一个只包含字符‘0’（代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。
在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0,y0),(x1,y1),...,(xk−1,yk−1)，其中(x(i+1)%k,y(i+1)%k)是由(xi,yi)(x_0, y_0),(x_1, y_1), . . . ,(x_{k−1}, y_{k−1})，其中(x_{(i+1)\%k} , y_{(i+1)\%k}) 是由 (x_i , y_i) 通过上/下/左/右移动一次得来的 (0 ≤ i ≤ k − 1)，
此时这 k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。
请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。

解题思路：

由于不需要考虑子岛屿的个数，我们只需要从海水开始直接使用BFS遍历，如果遇到海水就将其标记为已遍历，然后遍历其上下左右的邻接节点；如果遇到未遍历过的岛屿，就将岛屿个数加一，然后单独使用一次BFS遍历整个岛屿，在这一层BFS遍历中，只遍历未被检索的岛屿节点并将其标记为已遍历，由于整个外圈岛屿都已经被标记，所以就不会出现一个岛屿被当成多个岛屿的情况。
为了简化边缘的处理，可以直接在原地图外围增加一圈海水。这样就可以确保不会出现初始节点选在某一个岛屿内部的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
next_p = [(0,1),(1,0),(0,-1),(-1,0)]
next_q = [(1,0),(0,1),(-1,0),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]
def search_island(x,y):
    global sea_map
    global visited
    # BFS  
    q = []
    q.append((x,y))
    while q:
        x1,y1 = q[0][0], q[0][1]
        q.pop(0)
        if visited[x1][y1]:
            continue
        # only search the island
        visited[x1][y1] = 1
        for d in next_p:
            if sea_map[x1+d[0]][y1+d[1]] == '1' and visited[x1+d[0]][y1+d[1]] == False:
                q.append((x1+d[0], y1+d[1]))

t = int(input())
sea_map = []
visited = []
for i in range(t):
    # initialize
    sea_map = []
    visited = []
    m,n = map(int, input().split())
    sea_map.append('0'*(n+2))
    for j in range(m):
        sea_map.append('0' + input() + '0')
    sea_map.append('0'*(n+2))
    visited = [[0]*(n+2) for k in range(m+2)]
    # bfs
    ans = 0
    q = []
    q.append((0,0))
    while q:
        x, y = q[0][0], q[0][1]
        q.pop(0)
        if visited[x][y]:
            continue
        # begin to visit this node
        if sea_map[x][y] == '0':
            # sea
            visited[x][y] = 1
            # push the nodes that near it into the queue
            for d in next_q:
                if  0 <= x+d[0] <= m+1 and 0 <= y+d[1] <= n+1 and visited[x+d[0]][y+d[1]] == False:
                    q.append((x+d[0], y+d[1]))
        else:
            # island
            ans += 1
            search_island(x,y)
    print(ans)
    for line in visited:
        print(line)

例题 2：最少的1（蓝桥杯第13届国赛）

题目描述：

给定1个正整数nn，找出所有nn的倍数中，用二进制表示法表示下1的个数最少是多少？

输入格式：

输入一行包含一个整数nn

输出格式：

输出一行包含一个整数表示答案

解题思路：

二进制数的特殊进位方式 + 同余最短路径 我们希望找到一个 n 的倍数，它的二进制只包含 0 和 1。问题转换为要从只由 1 和 0 构成的二进制数中，挑选一个最小的 n 的倍数。也就是将所有只包含 0 和 1 的十进制数（例如 1，10，11，100，101，…）按构造顺序尝试，直到找到一个是 n 的倍数为止。但因为这些数太多，不能直接枚举数值，而是使用BFS + 模 n 的余数来避免爆炸。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
   易知直接研究n的倍数的二进制进位是很难的，在进位过程中1的个数并没有明确的规律，需要绕开进位思考
   注意到2进制数的递推有两种形式：
    1.二进制01串末尾加1个0
    2.二进制01串末尾加1个1
   这个进位规则可以覆盖到所有的数，所以是一种有效的规则，尽管它在数值上不是递增的，但由于避免了进位，所以在1的个数上是不减的
   这两种递推关系可以生成一棵树，每条边权值为1，第一个通过这种方式被找到的n的倍数拥有最少的1，题目由此变成最短路径问题，可以使用BFS解决
*/

#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

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

    vector<bool> visited(n, false);
    queue<pair<string, int>> q;

    // 初始状态是 "1"，mod 为 1 % n
    q.push({"1", 1 % n});
    visited[1 % n] = true;

    while (!q.empty()) {
        auto [s, r] = q.front();
        q.pop();

        if (r == 0) {
            cout << s << endl;
            return 0;
        }

        // 添加 '0'
        int r0 = (r * 10) % n;
        if (!visited[r0]) {
            visited[r0] = true;
            q.push({s + "0", r0});
        }

        // 添加 '1'
        int r1 = (r * 10 + 1) % n;
        if (!visited[r1]) {
            visited[r1] = true;
            q.push({s + "1", r1});
        }
    }
    return 0;
}