题目描述
思路解析动画文字版
记住「记原色 → 栈里弹一个、染四周同色的、再入栈」,下面逐帧套它。
先看起点 (1, 1)(紫色),它的原色 old = 1。我们要把和它连通的同色格子都染成 2。
判一下:新色 2 和原色 1 不一样,不会出现「越染越像原色」的死循环,可以放心开染。要是两者相等,这一步就该直接返回了。
先把起点 (1, 1) 染成 2(变绿),压进栈。接下来不断从栈里弹格子、向四周扩散。
从栈顶弹出 (1, 1)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
往上看邻居 (0, 1):它还是原色 1,和起点同色又挨着,符合条件,要把它也染上。
把 (0, 1) 染成 2(变绿)、压进栈,等会儿再从它向外扩。
往左看邻居 (1, 0):它还是原色 1,和起点同色又挨着,符合条件,要把它也染上。
把 (1, 0) 染成 2(变绿)、压进栈,等会儿再从它向外扩。
从栈顶弹出 (1, 0)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
往下看邻居 (2, 0):它还是原色 1,和起点同色又挨着,符合条件,要把它也染上。
把 (2, 0) 染成 2(变绿)、压进栈,等会儿再从它向外扩。
往上看邻居 (0, 0):它还是原色 1,和起点同色又挨着,符合条件,要把它也染上。
把 (0, 0) 染成 2(变绿)、压进栈,等会儿再从它向外扩。
从栈顶弹出 (0, 0)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
从栈顶弹出 (2, 0)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
从栈顶弹出 (0, 1)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
往右看邻居 (0, 2):它还是原色 1,和起点同色又挨着,符合条件,要把它也染上。
把 (0, 2) 染成 2(变绿)、压进栈,等会儿再从它向外扩。
从栈顶弹出 (0, 2)(紫色),挨个查它的上下左右四个邻居,把还是原色 1 的染掉。
栈空了,扩散结束。这一片四连通的 1 全被染成了 2(绿色),一共 6 个格子;右下角那个 1 被 0 隔开、够不着,保持不变。最终网格就是答案。
边界:同色直接返回、孤立点只染自己、全同色整张染。
两个高频追问:DFS/BFS 等价;染色即标记、免去 visited。
参考代码
from typing import Listclass Solution: def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]: old = image[sr][sc] if old == color: return image m, n = len(image), len(image[0]) stack = [(sr, sc)] image[sr][sc] = color while stack: r, c = stack.pop() for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r + dr, c + dc if 0 <= nr < m and 0 <= nc < n and image[nr][nc] == old: image[nr][nc] = color stack.append((nr, nc)) return image复杂度
- 时间：O(m·n)，每个格子最多被染一次、入栈出栈各一次,m、n 是网格的行数和列数
- 空间：O(m·n)，最坏情况(整张图同色)栈里会装下几乎所有格子;递归写法则是递归栈同量级
易错点
面试追问把动画讲成自己的话
追问用 DFS 还是 BFS?有区别吗?
追问可以不用额外的 visited 数组吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
寻找图中是否存在路径
LeetCode 1971 · 简单 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题