算法沉淀——BFS 解决 FloodFill 算法(leetcode真题剖析)

博主：小蓝
发布时间：2025 年 09 月 13 日
110 次浏览
暂无评论
1145字数
分类： Linux 技术杂烩

下面把 BFS 思路讲清，并给出可直接通过的 Flood Fill（如 LeetCode 733）解法与对比表 ✅

## 一、问题与核心思路

给定图像 `image[h][w]`、起点 `(sr, sc)` 与 新颜色 `newColor`，把与起点同色、且通过 四方向（上/下/左/右）连通的所有像素都染成 `newColor`。
关键：用 队列 层层扩散，避免递归栈溢出；若起点色与 `newColor` 相同，直接返回（否则会**死循环**）。🙂

```mermaid
flowchart LR
A[读入 image, sr, sc, newColor] --> B{起点色 == newColor?}
B -- 是 --> Z[返回 image]
B -- 否 --> C[入队 (sr,sc)]
C --> D{队列非空?}
D -- 否 --> Z
D -- 是 --> E[出队 (r,c)]
E --> F[将 image[r][c] 染为 newColor]
F --> G[遍历4邻居候选]
G --> H{越界/不同色?}
H -- 是 --> D
H -- 否 --> I[入队邻居并继续]
I --> D
```

---

## 二、BFS 代码（Python，可直接运行）

```python
from collections import deque

def floodFill(image, sr, sc, newColor):
    h, w = len(image), len(image[0])
    src = image[sr][sc]
    if src == newColor:      # ① 重要剪枝：同色直接返回
        return image

q = deque([(sr, sc)])    # ② 队列初始化
    image[sr][sc] = newColor # ③ 先染色再入队的也可，本解选择入队后第一时间染色
    dirs = [(1,0),(-1,0),(0,1),(0,-1)]  # ④ 四方向

while q:                 # ⑤ 典型 BFS 模板
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r+dr, c+dc
            # ⑥ 边界判断 + 颜色判断：仅把“与起点同色”的邻居推进来
            if 0 <= nr < h and 0 <= nc < w and image[nr][nc] == src:
                image[nr][nc] = newColor   # ⑦ 染色即“标记已访问”，避免重复入队
                q.append((nr, nc))
    return image
```

**解释（逐段）**：

* `①`：若 起点色 与 `newColor` 相同，不做任何改动，可避免无休止的扩散。
* `②`：使用 `deque` 实现 队列，`O(1)` 出入队。
* `③`：把起点染为 新颜色，也等价于“已访问标记”。
* `④`：只走 四方向；若题目要求八方向，扩展为 8 个增量即可。
* `⑤`：循环直到队列为空，完成一圈圈的层级扩展。
* `⑥`：两重判定（不越界、与起点同色）保证正确范围。
* `⑦`：染色即访问标记，防止重复入队；不需要额外 `visited` 数组，空间更省。

---

## 三、复杂度与边界

* 时间复杂度：访问每个像素至多一次，`O(h*w)`。
* 空间复杂度：队列最坏装下整层像素，`O(h*w)`。
* 边界注意：
  1. 起点不合法（一般题目保证合法）。
  2. 起点色等于 新颜色（需**提前返回**）。
  3. 大图像时优先 BFS，避免深递归导致栈溢出（🚫 过深 DFS）。

---

## 四、BFS vs DFS（vditor/Markdown 支持）

| 维度     | BFS            | DFS                    |
| -------- | -------------- | ---------------------- |
| 思路     | 队列逐层扩散   | 递归/栈深入扩散        |
| 风险     | 需要额外队列   | 递归深度过大可能栈溢出 |
| 记忆化   | 染色即标记访问 | 同                     |
| 实战推荐 | 大图更稳       | 小规模可选，代码短     |

---

## 五、易错点清单（踩坑必看）🚧

1. **忘记剪枝**：`src == newColor` 必须提前返回。
2. **未即时标记**：把邻居入队后应**立刻染色**，否则会被多次入队。
3. **越界判断顺序**：先判越界再访问像素，避免数组越界。
4. **方向集维护**：四方向增量统一放在 `dirs` 中，减少手写错误。

---

## 六、最小测试（手动校验示例）

```text
输入:
image =
1 1 1
1 1 0
1 0 1
sr=1, sc=1, newColor=2

输出:
2 2 2
2 2 0
2 0 1
```

**解释**：起点 `(1,1)` 的连通块是所有原色为 `1` 且与其通过四方向连通的像素；最终这些像素被统一染成 2。

---

## 七、总结

* 用 BFS 做 Flood Fill：**队列扩散 + 染色即标记 + 提前剪枝**；
* 复杂度线性、实现稳健；对大尺寸图像更可靠。
  把这套模板固定下来，再遇到“同色连通块”问题，直接替换判定条件即可完成。🎯

蓝易云是一家专注于香港及国内数据中心服务的提供商，提供高质量的服务器租用和云计算服务、包括免备案香港服务器、香港CN2、美国服务器、海外高防服务器、国内高防服务器、香港VPS等。致力于为用户提供稳定,快速的网络连接和优质的客户体验。

最后修改：2025 年 09 月 13 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

算法沉淀——BFS 解决 FloodFill 算法(leetcode真题剖析)

小蓝 • 2025 年 09 月 13 日

下面把 BFS 思路讲清，并给出可直接通过的 Flood Fill（如 LeetCode 733）解法与对比表 ✅

## 一、问题与核心思路

---

## 二、BFS 代码（Python，可直接运行）

```python
from collections import deque

def floodFill(image, sr, sc, newColor):
    h, w = len(image), len(image[0])
    src = image[sr][sc]
    if src == newColor:      # ① 重要剪枝：同色直接返回
        return image

**解释（逐段）**：

---

## 三、复杂度与边界

---

## 四、BFS vs DFS（vditor/Markdown 支持）

---

## 五、易错点清单（踩坑必看）🚧

---

## 六、最小测试（手动校验示例）

```text
输入:
image =
1 1 1
1 1 0
1 0 1
sr=1, sc=1, newColor=2

输出:
2 2 2
2 2 0
2 0 1
```

**解释**：起点 `(1,1)` 的连通块是所有原色为 `1` 且与其通过四方向连通的像素；最终这些像素被统一染成 2。

---

## 七、总结

算法沉淀——BFS 解决 FloodFill 算法(leetcode真题剖析)

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

微信视频号视频下载工具WeChatVideoDownloader

Win11系统优化工具-Windows11一键设置

YDArk - 系统内核工具

XPay-自建个人免签收款支付系统

Windows微软常用运行库合集一键安装

Linux命令拓展：为cp和mv添加进度显示

OSSEC在Ubuntu下的搭建与配置

MySQL字符串函数使用技巧

C#多线程锁机制及性能对比分析

CentOS与Ubuntu中防火墙配置命令集汇

算法沉淀——BFS 解决 FloodFill 算法(leetcode真题剖析)

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

算法沉淀——BFS 解决 FloodFill 算法(leetcode真题剖析)

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款