洪水填充算法

发表于 更新于 分类于 Waline：

最近看到了一个编程大赛是用程序去走迷宫，其中提到了一种比较有趣的方式，叫做洪水填充算法，它模拟的是在假设我们在一个迷宫的入口注水，如果有出口，水必定会从出口流出的这个过程，听起来比较有趣，于是看了一下其算法思想。

什么是洪水填充算法

洪水填充算法是一种用于图像处理和计算机图形学中的算法，用于将特定区域内的像素值替换为新的值。它从一个种子点开始，将相邻的像素逐个加入到一个队列中，并逐个处理队列中的像素，直到队列为空。处理过程中，可以根据特定的条件来判断是否将相邻的像素加入队列，以控制填充的范围。

洪水填充(也称为种子填充)是一种算法，用于确定连接到多维数组中给定节点的区域。

它用于绘画程序的“桶”填充工具，以用不同的颜色填充连接的、类似颜色的区域，并在围棋和扫雷等游戏中用于确定哪些棋子被清除。当应用于图像以用颜色填充特定的有界区域时，它也称为边界填充。

洪水填充算法采用三个参数：起始节点、目标颜色和替换颜色。

考虑左边的以下矩阵——如果起始节点是 (3, 9)，目标颜色为 “BLACK” 替换颜色是 “GREY”，该算法在矩阵中查找所有通过目标颜色的路径连接到起始节点的节点，并将它们更改为替换颜色。

洪水填充算法与BFS，DFS的关系

BFS和DFS是用于图的遍历的算法，它们可以用于搜索图中的节点或路径。它们的主要区别在于遍历的顺序不同。

BFS是一种层次遍历算法，从起始节点开始，依次访问其所有的相邻节点，然后再访问相邻节点的相邻节点，以此类推。BFS使用队列来保存待访问的节点，保证了按照层次进行遍历。

DFS是一种深度遍历算法，从起始节点开始，沿着一条路径一直遍历到底，直到无法继续深入为止，然后回溯到上一个节点，继续遍历其他路径。DFS使用栈来保存待访问的节点，保证了深度优先的特性。

洪水填充算法可以看作是一种特殊的BFS算法，它在图像中以种子点为起始节点，按照广度优先的方式进行遍历，直到无法再扩展。因此，可以说洪水填充算法是BFS的一种应用。

另外，洪水填充算法也可以使用DFS来实现，只需将栈替换为递归调用即可。但是相比于BFS，DFS在洪水填充算法中可能会导致堆栈溢出的问题，因为DFS会一直深入直到无法再扩展，而图像中的区域可能非常大，导致递归调用层次过深。

综上所述，洪水填充算法与BFS和DFS有一定的关系，可以将其看作是BFS的一种特殊应用，而DFS也可以用于实现洪水填充算法，但需要注意堆栈溢出的问题。

洪水填充算法的实现

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
from collections import deque
 
 
# 下面列出了所有八种可能的动作
row = [-1, -1, -1, 0, 0, 1, 1, 1]
col = [-1, 0, 1, -1, 1, -1, 0, 1]
 
 
# 检查是否可以从像素 (x, y)
# 当前像素。函数返回 false 如果像素
# 颜色不同，或者不是有效像素
def isSafe(mat, x, y, target):
    return 0 <= x < len(mat) and 0 <= y < len(mat[0]) and mat[x][y] == target
 
 
# 使用 BFS 进行洪水填充
def floodfill(mat, x, y, replacement):
 
    # 基础案例
    if not mat or not len(mat):
        return
 
    # 创建Queue并入队起始像素
    q = deque()
    q.append((x, y))
 
    # 获取目标颜色
    target = mat[x][y]
 
    #目标颜色与替换相同
    if target == replacement:
        return
 
    # Queue变空时#中断
    while q:
 
        # 将前端节点出列并处理
        x, y = q.popleft()
 
        # 用替换的像素颜色替换当前像素颜色
        mat[x][y] = replacement
 
        # 处理当前像素的所有八个相邻像素并
        # 将每个有效像素排入Queue
        for k in range(len(row)):
            # 如果位置 (x + row[k], y + col[k]) 处的相邻像素是
            #有效，与当前像素颜色相同
            if isSafe(mat, x + row[k], y + col[k], target):
                # 将相邻像素排入Queue
                q.append((x + row[k], y + col[k]))
 
 
if __name__ == '__main__':
 
    # 矩阵显示具有不同颜色的屏幕部分
    mat = [
            ['Y', 'Y', 'Y', 'G', 'G', 'G', 'G', 'G', 'G', 'G'],
            ['Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'G', 'X', 'X', 'X'],
            ['G', 'G', 'G', 'G', 'G', 'G', 'G', 'X', 'X', 'X'],
            ['W', 'W', 'W', 'W', 'W', 'G', 'G', 'G', 'G', 'X'],
            ['W', 'R', 'R', 'R', 'R', 'R', 'G', 'X', 'X', 'X'],
            ['W', 'W', 'W', 'R', 'R', 'G', 'G', 'X', 'X', 'X'],
            ['W', 'B', 'W', 'R', 'R', 'R', 'R', 'R', 'R', 'X'],
            ['W', 'B', 'B', 'B', 'B', 'R', 'R', 'X', 'X', 'X'],
            ['W', 'B', 'B', 'X', 'B', 'B', 'B', 'B', 'X', 'X'],
            ['W', 'B', 'B', 'X', 'X', 'X', 'X', 'X', 'X', 'X']
    ]
 
    #启动节点
    x = 3
    y = 9
 
    # 具有目标颜色`X`
    #替换色
    replacement = 'C'
 
    # 用替换色替换目标色
    floodfill(mat, x, y, replacement)
 
    # 更换后打印颜色
    for r in mat:
        print(r)

DFS

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
57
58
59
60
61
62
63
64
65
66
67
# 下面列出了所有八种可能的动作
row = [-1, -1, -1, 0, 0, 1, 1, 1]
col = [-1, 0, 1, -1, 1, -1, 0, 1]
 
 
# 检查是否可以从像素 (x, y)
# 当前像素。函数返回 false 如果像素
# 颜色不同，或者不是有效像素
def isSafe(mat, x, y, target):
    return 0 <= x < len(mat) and 0 <= y < len(mat[0]) and mat[x][y] == target
 
 
# 使用 DFS 进行洪水填充
def floodfill(mat, x, y, replacement):
 
    # 基础案例
    if not mat or not len(mat):
        return
 
    # 获取目标颜色
    target = mat[x][y]
 
    #目标颜色与替换相同
    if target == replacement:
        return
 
    # 用替换的像素颜色替换当前像素颜色
    mat[x][y] = replacement
 
    # 处理当前像素的所有八个相邻像素并
    # 每个有效像素重复
    for k in range(len(row)):
 
        # 如果位置 (x + row[k], y + col[k]) 处的相邻像素是
        # 一个有效像素，与当前像素颜色相同
        if isSafe(mat, x + row[k], y + col[k], target):
            floodfill(mat, x + row[k], y + col[k], replacement)
 
 
if __name__ == '__main__':
 
    # 矩阵显示具有不同颜色的屏幕部分
    mat = [
            ['Y', 'Y', 'Y', 'G', 'G', 'G', 'G', 'G', 'G', 'G'],
            ['Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'G', 'X', 'X', 'X'],
            ['G', 'G', 'G', 'G', 'G', 'G', 'G', 'X', 'X', 'X'],
            ['W', 'W', 'W', 'W', 'W', 'G', 'G', 'G', 'G', 'X'],
            ['W', 'R', 'R', 'R', 'R', 'R', 'G', 'X', 'X', 'X'],
            ['W', 'W', 'W', 'R', 'R', 'G', 'G', 'X', 'X', 'X'],
            ['W', 'B', 'W', 'R', 'R', 'R', 'R', 'R', 'R', 'X'],
            ['W', 'B', 'B', 'B', 'B', 'R', 'R', 'X', 'X', 'X'],
            ['W', 'B', 'B', 'X', 'B', 'B', 'B', 'B', 'X', 'X'],
            ['W', 'B', 'B', 'X', 'X', 'X', 'X', 'X', 'X', 'X']
        ]
 
    #启动节点
    x, y = (3, 9)   # 具有目标颜色`X`
 
    #替换色
    replacement = 'C'
 
    # 使用 DFS 将目标颜色替换为替换颜色
    floodfill(mat, x, y, replacement)
 
    # 更换后打印颜色
    for r in mat:
        print(r)

使用洪水填充算法解迷宫

洪水填充算法（Flood Fill Algorithm）通常用于填充连通区域。虽然它不是用于解决迷宫最短路径问题的常规算法，但我们可以将其稍作修改来实现这个目标。

以下是使用洪水填充算法解决迷宫最短路径问题的步骤：

  1. 创建一个与迷宫相同大小的二维数组，用于表示迷宫的状态。初始状态下，所有的格子都被标记为未访问状态。

  2. 选择一个起始点作为洪水的源点，并将其标记为已访问状态。

  3. 将源点加入到一个队列中。

  4. 进入循环，直到队列为空：

  • 从队列中取出一个格子。
  • 检查该格子的上、下、左、右四个邻居格子：
    • 如果邻居格子是终点，说明找到了最短路径，可以结束算法。
    • 如果邻居格子是通路（未访问状态），将其标记为已访问状态，并将其加入队列中。

  1. 如果队列为空，说明无法找到最短路径。

  2. 反向追踪标记的路径，从终点开始，根据每个格子周围的已访问格子找到最短路径。

这种方法基于广度优先搜索（BFS）的思想，通过逐层遍历迷宫来找到最短路径。洪水填充算法的核心思想是从源点开始，逐渐扩散到周围的格子，直到达到目标点。

请注意，这种方法并不保证找到迷宫的最短路径，但它是一种简单且直观的方法，可以用于解决一般情况下的迷宫问题。对于复杂的迷宫，可能需要使用其他更高级的算法来找到最短路径。