python用广度优先搜索实现种子填充算法

在Python中，我们可以使用广度优先搜索（BFS，Breadth-First Search）来实现种子填充算法，也称为连通组件或区域填充算法。这个算法通常用于图像处理、游戏开发等场景，目标是找出由给定种子点开始的所有相邻像素。

以下是一个基本的步骤和代码示例：

1. **创建队列**：从起始种子点开始，将其加入队列。
2. **定义邻居规则**：根据应用场景，确定哪些相邻像素属于同一区域，比如二维数组中的上下左右四个方向。
3. **遍历队列**：取出队列的第一个元素，检查其周围的邻域，将符合条件的新节点添加到队列并标记为已访问。
4. **递归过程**：重复步骤3，直到队列为空，表示所有可达的节点都已处理。
5. **结果存储**：在完成遍历后，得到的结果就是由种子点形成的区域。

下面是简化版的Python代码实现：

from collections import deque

def bfs_seed_fill(image, seed):
    rows, cols = len(image), len(image)
    visited = [[False] * cols for _ in range(rows)]
    queue = deque([seed])
    visited[seed][seed] = True

    while queue:
        x, y = queue.popleft()
        if x < 0 or x >= rows or y < 0 or y >= cols or image[x][y] == 0:
            continue

        # 假设上下左右四个方向为邻居
        neighbors = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
        
        for nx, ny in neighbors:
            if not visited[nx][ny]:
                image[nx][ny] = image[x][y]
                visited[nx][ny] = True
                queue.append((nx, ny))

# 示例
image = [
    [0, 1, 0],
    [1, 1, 1],
    [0, 1, 0]
]
seed = (0, 0)
bfs_seed_fill(image, seed)
print(image)  # 输出：[[1, 1, 1], [1, 1, 1], [1, 1, 1]]