前言

广度优先搜索算法(BFS)在各大算法竞赛中非常常见,对于我这种没有系统性学习过算法的人来说已经是进阶难度了,费了很大劲才厘清BFS的核心思路,勉强AC了一道最简单的BFS题
附上freeCodeCamp中关于BFS和DFS的中文教程:
https://www.freecodecamp.org/chinese/learn/python-v9/lecture-understanding-graphs-and-trees/how-do-depth-first-and-breadth-first-search-work

正文

顾名思义,BFS注重的是广度,需要从起点开始,遍历所有相邻的节点,用一个队列(deque)存放已遍历的节点,每次遍历时,移除队列的当前节点并将其所有未访问的相邻节点添加到队列中,并标记为已访问.
遍历完所有节点后队列会变为空,bfs结束
由此得出的模版(以标准矩形宫格图为例):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def bfs(start,graph):
    from collections import deque
    q = deque(start)

    directions = [(1,0),(-1,0),(0,1),(0,-1)]  #得到相邻节点的所有方向
    visited = [[False]*n for _ in range(n)]   #标记是否访问
    visited[start[0]][start[1]] = True

    while q: #当队列不为空时
        x,y = q.popleft()

        for dx,dy in directions:

            if 0 <= x+dx < n and 0 <= y+dy < n:  #检查是否越界

                if not visited[x+dx][y+dy]:  #检查是否访问过

                    q.append((x+dx,y+dy))
                    visited[x+dx][y+dy] = True

freeCodeCamp上的讲解更加清晰详细,还给出了图解,如果这个伟大的开源项目对你也有帮助,强烈建议你赞助它

原题复现

https://www.luogu.com.cn/problem/P1162

题目描述

由数字 00 组成的方阵中，有一任意形状的由数字 11 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 22。例如：6×66\times 6 的方阵（n=6n=6），涂色前和涂色后的方阵如下：

如果从某个 00 出发，只向上下左右 44 个方向移动且仅经过其他 00 的情况下，无法到达方阵的边界，就认为这个 00 在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的 00 是连通的（两两之间可以相互到达）。

1
2
3
4
5
6
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1
1
2
3
4
5
6
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数 n(1≤n≤30)n(1 \le n \le 30)。

接下来 nn 行，由 00 和 11 组成的 n×nn \times n 的方阵。

方阵内只有一个闭合圈，圈内至少有一个 00。

输出格式

已经填好数字 22 的完整方阵。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

输出 #1

1
2
3
4
5
6
7
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

说明/提示

对于 100%100\% 的数据，1≤n≤301 \le n \le 30。

解题思路

对于这道题,需要反直觉的思路,遍历不在闭合圈内的0并标记,因为找到闭合圈内的一个0作为起点是不容易的,但找到闭合圈外的0是很简单的
结合上文的介绍,答案已经呼之欲出:

代码实现

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
import sys
from collections import deque
n = int(input())

grid = []
for _ in range(n):
    row = list(map(int,sys.stdin.readline().split()))
    grid.append(row)
    
dire = [(1,0),(0,1),(-1,0),(0,-1)]
q = deque()

for i in range(n):
    for j in range(n):
        if grid[i][j] == 0 and (i == 0 or j == 0 or i == n-1 or j == n-1):
            grid[i][j] = 3
            q.append((i,j))


while q:
    x,y = q.popleft()
    for dx,dy in dire:
        if 0 <= x+dx <= n-1 and 0 <= y+dy <= n-1:
            if grid[x+dx][y+dy] == 0:
                grid[x+dx][y+dy] = 3
                q.append((x+dx,y+dy))

for i in range(n):
    for j in range(n):
        if grid[i][j] == 0:
            grid[i][j] = 2
        elif grid[i][j] == 3:
            grid[i][j] = 0

        print(grid[i][j],end = " ")
    print()

这种实现采用了将0变成3的标记方式,而没有使用visited二维数组,很大程度上节省了内存空间
这时候有人(其实是我自己这个蠢货)要问了:煮啵煮啵,你初始化怎么只在最外围找0,如果最外围没有0你不炸了吗
最外围没有0那不更简单了吗,q为空直接不进入循环,而最外围是一整圈的1无疑包围了所有的0,我们的代码仍能实现将所有的0都变成2,AC就完了