What is the main pattern used in the Flood Fill problem?

The primary pattern is Array plus Depth-First Search, as you explore all connected pixels recursively or iteratively.

Can I use BFS instead of DFS for Flood Fill?

Yes, BFS is valid and often used to avoid stack overflow in large grids while achieving the same result.

What should I do if the starting pixel already has the target color?

Skip any operation and return the image immediately to prevent unnecessary recursion or queue processing.

Does Flood Fill consider diagonal connections?

By default, only horizontal and vertical connections are considered; diagonals are a variant extension.

What is the time and space complexity of Flood Fill?

Time complexity is O(N) where N is the number of pixels, and space complexity is O(N) due to recursion stack or queue.

#733

Easy

auto_awesome图·搜索

LeetCode 题解工作台

图像渲染

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行上色填充。为了完成上色工作：从初始像素开始，将其颜色改为 co…

数组深度优先搜索广度优先搜索矩阵

题目描述

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行上色填充。

为了完成 上色工作：

从初始像素开始，将其颜色改为 color。
对初始坐标的 上下左右四个方向上 相邻且与初始像素的原始颜色同色的像素点执行相同操作。
通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续重复此过程。
当没有其它原始颜色的相邻像素时停止操作。

最后返回经过上色渲染修改后的图像。

示例 1:

输入：image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, color = 2

输出：[[2,2,2],[2,2,0],[2,0,1]]

解释：在图像的正中间，坐标 (sr,sc)=(1,1) （即红色像素）,在路径上所有符合条件的像素点的颜色都被更改成相同的新颜色（即蓝色像素）。

注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。

示例 2:

输入：image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0

输出：[[0,0,0],[0,0,0]]

解释：初始像素已经用 0 着色，这与目标颜色相同。因此，不会对图像进行任何更改。

提示:

m == image.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], color < 2¹⁶
0 <= sr < m
0 <= sc < n

lightbulb

解题思路

方法一：DFS

我们记初始像素的颜色为 $\textit{oc}$ ，如果 $\textit{oc}$ 不等于目标颜色 $\textit{color}$ ，我们就从 $(\textit{sr}, \textit{sc})$ 开始深度优先搜索，将所有符合条件的像素点的颜色都更改成目标颜色。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为二维数组 $\textit{image}$ 的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def floodFill(
        self, image: List[List[int]], sr: int, sc: int, color: int
    ) -> List[List[int]]:
        def dfs(i: int, j: int):
            image[i][j] = color
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < len(image) and 0 <= y < len(image[0]) and image[x][y] == oc:
                    dfs(x, y)

        oc = image[sr][sc]
        if oc != color:
            dirs = (-1, 0, 1, 0, -1)
            dfs(sr, sc)
        return image

speed

复杂度分析

指标	值
时间	complexity is O(N) where N is total pixels, as each pixel is visited once. Space complexity is O(N) in worst case due to recursion stack or queue storage.
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Checks if you recognize that a recursive DFS naturally models connected components in a grid.
question_mark
Looks for handling of edge conditions like starting pixel already having target color.
question_mark
Wants to see whether BFS alternative is considered for avoiding deep recursion stack.

warning

常见陷阱

外企场景

error
Modifying pixels before checking color can paint unintended areas.
error
Failing to handle the starting pixel being the same as the target color can cause infinite recursion.
error
Ignoring boundary conditions leads to index errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Use DFS with diagonal connections to extend flood fill to 8-direction connectivity.
arrow_right_alt
Perform flood fill on a 3D matrix for volumetric image processing.
arrow_right_alt
Implement color replacement with constraints, such as only changing pixels within a certain distance.

help

常见问题

外企场景

继续练习

#749 隔离病毒 #695 岛屿的最大面积 #778 水位上升的泳池中游泳