企业官网建设流程全解析

LeetCode 733：图像渲染 Flood Fill——从二维网格开始理解 DFS 和 BFS

一、准备做 200，可以先做这道题

LeetCode 733：图像渲染

我原本准备做 LeetCode 200「岛屿数量」，但刚开始接触二维网格搜索时，对“从一个点向四周搜索”这件事还不是特别熟悉。

所以可以先做 733。

这道题可以帮助理解一个非常重要的模型：

从一个起点开始，把所有和它上下左右连通，并且数值相同的格子全部找出来。

这个模型其实就是后面 200「岛屿数量」的基础。

733 已经直接告诉了我们：

从哪里开始

我们只需要解决：

怎么从这个起点出发 把和它连起来的一整块区域全部找出来

而 200 则是在这个基础上，再增加一步：

自己去寻找每一座岛的起点

二、先理解二维网格中的“四个方向”

刚开始我以为：

从初始点出发，分别往上、下、左、右一直遍历。

但实际上并不是沿着四条直线一直扫。

假设当前格子的坐标是：

(row, col)

那么它紧挨着的四个格子分别是：

上：(row - 1, col) 下：(row + 1, col) 左：(row, col - 1) 右：(row, col + 1)

也就是说，我们每一次只检查当前格子周围的一格。

如果某个相邻格子符合要求，就进入这个格子，然后再从这个新格子继续检查它自己的上、下、左、右。

例如：

1 1 0 0 1 1 0 0 1

从左上角(0,0)开始，可以一路找到：

(0,0) → (0,1) ↓ (1,1) → (1,2) ↓ (2,2)

所以真正的思路是：

每到达一个新的格子，都重新检查它自己的四个邻居。

1、怎么保证四个方向一个都不会漏？

可以先把四个方向统一保存下来：

directions=[(-1,0),# 上(1,0),# 下(0,-1),# 左(0,1)# 右]

之后每到达一个格子，就执行：

fordr,dcindirections:new_row=row+dr new_col=col+dc

例如当前在：

(row, col)

四轮循环分别会得到：

row - 1, col row + 1, col row, col - 1 row, col + 1

所以可以把：

dr dc

理解成：

这一轮，行和列分别要变化多少

例如：

(-1, 0)

表示：

行 -1 列不变

也就是向上移动一格。

只要每一个到达的格子都执行一次这个for，它的四个方向就不会漏掉。

2、首先要记住起点原来的颜色

题目要求修改的是：

与初始位置上下左右连通，并且和初始位置颜色相同的格子。

所以最开始应该先保存起点原来的颜色：

original=image[sr][sc]

例如：

image[sr][sc] = 1

那么：

original = 1

之后我们寻找邻居时，就可以判断：

image[new_row][new_col]==original

只有颜色仍然等于起点原来的颜色，才属于我们需要继续寻找的区域。

3、还要判断有没有越界

二维数组不是无限大的。

假设：

rows=len(image)cols=len(image[0])

分别表示：

rows = 总行数 cols = 总列数

那么合法坐标必须满足：

0<=new_row<rows0<=new_col<cols

为什么是这样？

比如总共有 3 行：

第 0 行 第 1 行 第 2 行

合法行下标其实就是：

0 ~ rows - 1

所以写成：

0<=new_row<rows

列也是同样的道理。

PS: 这里判断的是整张图像的边界

三、先不管 DFS 和 BFS，这道题到底应该怎么想？

现在已经知道：

当前格子 → 有上、下、左、右四个邻居

但真正的问题是：

从起点(sr, sc)开始，怎么把所有和它连通、并且颜色相同的格子全部找出来？

假设：

1 1 0 0 1 1 0 0 1

起点是：

(0,0)

起点颜色是：

1

所以我们的目标就是：

从 (0,0) 出发 通过上下左右移动 把所有能够到达的 1 找出来

1、先处理起点

起点本身肯定属于需要修改的区域。

假设新颜色是：

2

那么可以先把：

(0,0)

修改成：

2 1 0 0 1 1 0 0 1

现在(0,0)已经处理好了。

接下来应该干什么？

自然就是检查：

它周围有没有其他和它连在一起的1？

2、检查当前格子的四个邻居

当前位置：

(0,0)

它的四个邻居是：

上：(-1,0) 下：(1,0) 左：(0,-1) 右：(0,1)

但不是每个位置都可以进入。

一个邻居至少要满足：

1. 没有越界 2. 颜色还是 original

这里：

上：(-1,0) → 越界 左：(0,-1) → 越界 下：(1,0) → 颜色是 0 右：(0,1) → 颜色是 1

所以真正能够继续进入的是：

(0,1)

3、进入(0,1)以后怎么办？

来到：

(0,1)

以后，问题又变成了：

(0,1)周围还有没有和它连通的1？

也就是说，我们又要做一模一样的事情：

处理当前格子 ↓ 检查四个方向 ↓ 找到符合条件的邻居 ↓ 进入邻居 ↓ 再检查邻居自己的四周

例如可能形成：

(0,0) ↓ (0,1) ↓ (1,1) ↓ (1,2) ↓ (2,2)

这时候会发现一个很重要的特点：

每进入一个新格子，我们面对的其实还是同一个问题。

都是：

处理当前格子 + 寻找它符合要求的邻居 + 继续处理邻居

而这种“一个大问题里面，又出现了完全相同的小问题”的结构，就非常适合递归。

4、还要解决一个问题：不能一直走回来

例如有两个相邻的格子：

A B

A 可以走到 B。

但是来到 B 以后，B 左边又是 A。

如果完全不记录哪些格子已经处理过，就可能出现：

A → B → A → B → A...

一直来回走。

所以一个格子访问以后，必须留下一个：

我已经处理过

的标记。

这道题其实正好可以利用“修改颜色”来做这件事。

例如：

original = 1 color = 2

访问一个格子以后：

1 → 2

之后我们只允许进入：

image[new_row][new_col]==original

已经变成2的格子，自然不会再次满足：

2 == 1

所以：

修改颜色不仅完成了题目的要求，同时也相当于给这个格子做了 visited 标记。

不过，通常情况下，如果题目不能直接修改原网格，就会额外准备一个visited来记录哪些格子已经访问过。

最常见有两种写法。

方法一：二维布尔数组

假设：

rows=len(image)cols=len(image[0])

可以创建：

visited=[[False]*colsfor_inrange(rows)]

一开始所有位置都是：

False

表示：

还没有访问过

例如：

False False False False False False False False False

如果现在访问了：

(0,1)

就可以：

visited[0][1]=True

变成：

False True False False False False False False False

以后再准备进入一个邻居时，除了判断：

有没有越界

以及：

这个格子本身是否满足题目条件

还要多判断：

notvisited[new_row][new_col]

比如：

if(0<=new_row<rowsand0<=new_col<colsandnotvisited[new_row][new_col]andimage[new_row][new_col]==original):

一旦决定进入这个格子，就先：

visited[new_row][new_col]=True

表示：

这个格子已经被发现过了，之后不要再重复进入。

方法二：使用 set 保存坐标

也可以写：

visited=set()

访问一个格子以后：

visited.add((row,col))

例如：

visited.add((0,1))

那么：

visited

里面可能保存：

{(0,0), (0,1), (1,1)}

之后判断一个格子有没有访问过：

(new_row,new_col)notinvisited

就可以了。

所以一般的网格搜索其实是：

当前位置 ↓ 检查四个邻居 ↓ 判断有没有越界 ↓ 判断是否满足题目条件 ↓ 判断有没有访问过 ↓ 如果可以进入 ↓ 先标记 visited ↓ 再继续搜索

而 733 比较特殊，因为：

image[row][col]=color

本身就已经能看出：

这个格子访问过了

所以不需要再额外创建visited。

可以把两种情况简单记成：

如果可以安全修改原数组 → 经常直接修改原数组当 visited 如果不能修改原数组 → 单独建立 visited

5、一个特殊情况：新颜色和原颜色一样

假设：

original = 1 color = 1

那么修改：

1 → 1

其实什么都没有发生。

这样“修改颜色作为访问标记”的方法就失效了。

例如：

A → B → A → B...

仍然可能不断重复访问。

而且既然：

原颜色 == 新颜色

最终整张图片本来也不会发生任何变化，所以可以一开始直接：

iforiginal==color:returnimage

不用继续搜索。

四、方法一：DFS

前面已经自己推出了这样一个过程：

进入当前格子 ↓ 处理当前格子 ↓ 检查四个邻居 ↓ 发现符合要求的邻居 ↓ 进入邻居 ↓ 邻居继续做同样的事情

这其实就是 DFS。

DFS：

Depth First Search，深度优先搜索。

可以简单理解成：

找到一个能继续走的邻居以后，马上进入这个邻居，然后继续往更深处找。

1、为什么这里可以使用递归？

我们可以写一个函数：

dfs(row,col)

它只负责一件事：

处理当前位置(row, col)，然后寻找它能够继续进入的邻居。

进入当前格子以后：

image[row][col]=color

然后检查四个方向：

fordr,dcindirections:new_row=row+dr new_col=col+dc

如果新的位置：

① 没有越界 ② 颜色仍然等于 original

说明它也是这块连通区域的一部分。

那么接下来怎么办？

其实还是做和当前格子完全一样的事情：

dfs(new_row,new_col)

所以递归并不是突然冒出来的。

而是因为：

处理邻居的问题，和处理当前格子的问题完全一样。

2、DFS 大概是怎么走的？

例如：

1 1 0 0 1 1 0 0 1

从：

(0,0)

开始。

可能会一路：

(0,0) → (0,1) → (1,1) → (1,2) → (2,2)

DFS 的感觉就是：

发现能继续走 ↓ 马上进去 ↓ 再发现能继续走 ↓ 继续进去 ↓ 直到这条路走不下去

之后递归才会一层一层返回，继续检查之前还没有检查完的其他方向。

3、DFS 完整代码

classSolution:deffloodFill(self,image:list[list[int]],sr:int,sc:int,color:int)->list[list[int]]:original=image[sr][sc]iforiginal==color:returnimage rows=len(image)cols=len(image[0])directions=[(-1,0),(1,0),(0,-1),(0,1)]defdfs(row,col):image[row][col]=colorfordr,dcindirections:new_row=row+dr new_col=col+dcif(0<=new_row<rowsand0<=new_col<colsandimage[new_row][new_col]==original):dfs(new_row,new_col)dfs(sr,sc)returnimage

整个 DFS 的核心其实就是：

dfs(当前格子) ↓ 先处理当前格子 ↓ 检查四个方向 ↓ 找到符合要求的邻居 ↓ dfs(邻居)

也就是：

进入一个格子 → 做标记 → 检查四个邻居 → 符合条件就继续进入。

五、方法二：BFS

理解 DFS 以后，再来看 BFS 就会自然很多。

DFS 的做法是：

发现一个邻居 ↓ 马上进入这个邻居 ↓ 继续往深处寻找

那么我也可以换一种方式：

发现一个邻居以后，我先不马上进去，而是先把它记下来，等之后再处理。

也就是说，我们需要一个地方保存：

已经发现，但是还没有检查它四周的格子。

这就是 BFS 中的队列queue。

1、为什么要使用队列？

假设当前处理 A：

A

然后发现两个邻居：

B C

我们暂时不马上进入 B 或 C，而是先记录：

待处理： B C

之后：

先处理 B 再处理 C

而 B 在处理过程中又可能发现：

D E

那么队列可能变成：

C D E

也就是说：

先发现的格子先处理。

这正好符合队列的：

先进先出 First In First Out(FIFO)

队列正常使用需要：

fromcollectionsimportdeque

2、初始化队列

queue=deque([(sr,sc)])

其中：

(sr,sc)

表示一个坐标。

例如(1, 2)表示：

第 1 行，第 2 列

外面的：

[(sr,sc)]

表示一个列表，作用是：把这个坐标作为一个整体，放进 deque 里。

因为 deque() 接收的是一个可以遍历的对象。
如果直接写：deque((sr, sc))
那么 (sr, sc) 会被拆开，变成：sr sc 两个元素。

而我们希望队列里保存的是：(sr, sc) 这样一个完整的坐标，所以外面需要再套一层列表。

3、popleft()是什么意思？

BFS 每次从队列最前面取出一个待处理格子：

row,col=queue.popleft()

例如：

queue = [(1,2), (1,3), (2,2)]

执行：

row,col=queue.popleft()

会取出：

(1,2)

于是：

row = 1 col = 2

队列剩下：

[(1,3), (2,2)]

接下来就开始检查：

(1,2)

自己的四个方向。

4、为什么找到邻居以后要加入队列？

假设处理(1,2)时，发现：

(1,3)

也是合法邻居。

这时候：

queue.append((1,3))

并不是说：

(1,3) 已经处理完了

而是表示：

我已经发现了(1,3)，但还没有检查它自己的四个方向，所以先放进待处理队列。

因此 BFS 的queue可以理解成：

已经发现，但还没有继续检查四周的格子。

5、为什么加入队列之前就要修改颜色？

BFS 中一般会这样写：

image[new_row][new_col]=color queue.append((new_row,new_col))

而不是等这个格子以后被：

popleft()

取出来的时候才修改颜色。

原因是：

一个格子可能同时被多个邻居发现。

例如：

A → C B → C

A 先发现 C。

如果只是：

queue.append(C)

但是没有立刻给 C 做标记，那么之后 B 检查邻居时，也会发现：

C 还是 original

于是又会：

queue.append(C)

最终：

C

被重复加入队列。

所以正确顺序应该是：

发现一个合法邻居 ↓ 立即修改颜色，表示已经发现过 ↓ 再放进 queue

也就是：

image[new_row][new_col]=color queue.append((new_row,new_col))

这里可以注意一个区别：

DFS

DFS 中：

dfs(new_row,new_col)

一进入函数，就马上：

image[row][col]=color

所以访问标记是在“进入 DFS 时”完成。

BFS

BFS 中邻居不会马上处理，而是先进入队列。

所以应该在：

加入队列之前

就做好标记，防止它在等待处理期间再次被其他格子加入。

6、BFS 完整代码

fromcollectionsimportdequeclassSolution:deffloodFill(self,image:list[list[int]],sr:int,sc:int,color:int)->list[list[int]]:original=image[sr][sc]iforiginal==color:returnimage rows=len(image)cols=len(image[0])directions=[(-1,0),(1,0),(0,-1),(0,1)]queue=deque([(sr,sc)])image[sr][sc]=colorwhilequeue:row,col=queue.popleft()fordr,dcindirections:new_row=row+dr new_col=col+dcif(0<=new_row<rowsand0<=new_col<colsandimage[new_row][new_col]==original):image[new_row][new_col]=color queue.append((new_row,new_col))returnimage

BFS 的整体过程就是：

起点放进 queue ↓ 给起点做标记 ↓ 从 queue 取出一个格子 ↓ 检查四个方向 ↓ 发现合法邻居 ↓ 立刻做标记 ↓ 把邻居加入 queue ↓ 继续处理 queue 中剩下的格子

六、DFS 和 BFS 到底是什么关系？

刚开始可能会觉得：

DFS 做完以后，是不是还可以继续优化成 BFS？

但其实不是。

DFS 和 BFS 并不是：

普通方法 ↓ 优化方法

而是：

两种不同的搜索顺序。

它们解决的都是：

从一个起点出发 把能够到达的所有位置找出来

区别主要在于：

下一步先处理谁？

1、DFS：一条路先走深

DFS：

发现邻居 ↓ 马上进入邻居 ↓ 继续寻找邻居 ↓ 一条路一直往深处走

递归 DFS 实际上借助的是：

函数调用栈

所以可以简单记成：

DFS → stack / 递归调用栈 → 一条路先走深

2、BFS：一层一层往外扩

BFS：

发现邻居 ↓ 先放进 queue ↓ 先把当前附近的格子处理掉 ↓ 再继续往外扩散

它使用的是：

队列 queue

所以可以记成：

BFS → queue → 一层一层往外扩

3、用同一张图来看区别

例如：

A / \ B C / \ D E

DFS 可能是：

A → B → D → 回到 B → E → 回到 A → C

因为：

找到一条路以后先一直走深

而 BFS 更像：

A → B、C → D、E

先处理离 A 一步的，再处理离 A 两步的。

所以：

DFS 和 BFS 找到的连通区域可能完全一样，只是访问顺序不同。

七、复杂度

假设图像大小为：

rows × cols

也就是一共有：

rows × cols

个格子。

最坏情况下，整张图所有格子都和起点连通。

那么每个格子最多被真正访问一次。

所以 DFS 和 BFS 的时间复杂度都是：

O(rows × cols)

1、DFS 的空间复杂度

递归 DFS 需要使用函数调用栈。

如果连通区域特别大，最坏情况下递归深度也可能达到：

rows × cols

所以空间复杂度最坏为：

O(rows × cols)

2、BFS 的空间复杂度

BFS 需要使用：

queue

最坏情况下队列中也可能同时保存大量格子。

所以最坏空间复杂度同样为：

O(rows × cols)

因此在这道题里：

BFS 并不是 DFS 的时间复杂度优化版本。

两者主要只是搜索方式不同。

不过 Python 中，递归 DFS 如果连通区域特别大，有可能因为递归层数过深出现：

RecursionError

这种情况下，可以考虑：

BFS

或者：

自己使用 stack 写迭代 DFS

避免依赖 Python 的递归调用栈。

八、这道题要学啥？

真正需要建立的是一个二维网格搜索模型：

从一个起点开始 ↓ 处理当前格子 ↓ 检查上、下、左、右 ↓ 判断有没有越界 ↓ 判断这个邻居能不能进入 ↓ 能进入就做访问标记 ↓ 继续从这个邻居向四周搜索

也就是：

从一个点出发，把与它连通的一整块区域全部找出来。

这里还有几个非常重要的思想。

第一，二维网格其实也可以理解成“点和点之间的连接”

每一个格子都可以看成一个点。

如果两个格子：

上下左右相邻

并且满足题目的移动条件，就可以认为：

两个点之间可以连接

所以 DFS 和 BFS 并不只是“树的算法”。

二维网格同样可以使用。

第二，要有 visited 的意识

搜索过程中最容易出现的问题就是：

A → B → A → B...

所以必须有办法判断：

这个位置我是不是已经处理过了？

733 比较特殊，可以直接用修改颜色代替：

visited

以后其他题不一定能修改原数组，就可能需要单独写：

visited=set()

或者：

visited=[[False]*colsfor_inrange(rows)]

第三，DFS 和 BFS 的核心问题其实一样

它们都在解决：

从当前点还能到哪里？

真正不同的是：

DFS：发现以后马上处理 BFS：发现以后先存起来，之后按照队列顺序处理