LeetCode: 733 Flood Fill

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a "flood fill" on the image starting from the pixel image[sr][sc].

To perform a "flood fill", consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

Example:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Explanation:

From the center of the image (pixel (1, 1)), all pixels connected by a path of the same color as the starting pixel are updated to the new color.

问题

图像由一个 m x n 的整数网格 image 表示，其中 image[i][j] 表示图像的像素值。

你还给出了三个整数 sr，sc 和 color。你应该从像素 image[sr][sc] 开始对图像执行“洪水填充”。

执行“洪水填充”时，考虑起始像素，以及与起始像素4方向连接的所有与起始像素颜色相同的像素，以及与这些像素4方向连接的像素（颜色也与起始像素相同），依此类推。将所有上述像素的颜色替换为 color。

在执行洪水填充后返回修改后的图像。

解决方案

深度优先搜索 (DFS) 和广度优先搜索 (BFS)

Approach 1: Depth-First Search (DFS) / 深度优先搜索 (DFS)

This approach uses DFS to explore and fill all connected pixels of the same color starting from the given pixel. We recursively visit each pixel in the 4 possible directions (up, down, left, right) and change its color if it matches the original color.

这种方法使用 DFS 来探索并填充从给定像素开始的所有相同颜色的连接像素。我们在4个可能的方向（上，下，左，右）递归访问每个像素，并在其颜色与原始颜色匹配时更改其颜色。

Implementation / 实现

Python

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original_color = image[sr][sc]
        if original_color == color:
            return image

        def dfs(r, c):
            if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]) or image[r][c] != original_color:
                return
            image[r][c] = color
            dfs(r - 1, c)
            dfs(r + 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)

        dfs(sr, sc)
        return image

Explanation / 解释

Check for No Operation Needed / 检查是否需要操作
```
original_color = image[sr][sc]
if original_color == color:
   return image
```
- English: If the original color at the starting pixel is the same as the new color, no changes are needed, and we return the image as is.
- Chinese: 如果起始像素的原始颜色与新颜色相同，则无需更改，我们直接返回图像。
DFS Function / DFS 函数
```
def dfs(r, c):
   if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]) or image[r][c] != original_color:
       return
   image[r][c] = color
   dfs(r - 1, c)
   dfs(r + 1, c)
   dfs(r, c - 1)
   dfs(r, c + 1)
```
- English: The dfs function changes the color of the current pixel and recursively visits all 4-directionally connected pixels that have the same original color.
- Chinese: dfs 函数更改当前像素的颜色，并递归访问所有具有相同原始颜色的4个方向连接的像素。
Start DFS from the Given Pixel / 从给定像素开始 DFS
```
dfs(sr, sc)
```
- English: We start the DFS from the given starting pixel (sr, sc).
- Chinese: 我们从给定的起始像素 (sr, sc) 开始 DFS。
Return the Modified Image / 返回修改后的图像
```
return image
```
- English: After performing the flood fill, we return the modified image.
- Chinese: 执行洪水填充后，我们返回修改后的图像。

Approach 2: Breadth-First Search (BFS) / 广度优先搜索 (BFS)

Alternatively, BFS can be used to perform the flood fill iteratively using a queue. BFS is typically more memory-efficient than DFS for problems involving large or deep grids.

另外，可以使用 BFS 来通过队列以迭代方式执行洪水填充。对于涉及大网格或深网格的问题，BFS 通常比 DFS 更节省内存。

BFS Implementation / BFS 实现

from collections import deque

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original_color = image[sr][sc]
        if original_color == color:
            return image

        rows, cols = len(image), len(image[0])
        queue = deque([(sr, sc)])

        while queue:
            r, c = queue.popleft()
            if image[r][c] == original_color:
                image[r][c] = color
                if r - 1 >= 0: queue.append((r - 1, c))
                if r + 1 < rows: queue.append((r + 1, c))
                if c - 1 >= 0: queue.append((r, c - 1))
                if c + 1 < cols: queue.append((r, c + 1))

        return image

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(m * n), where m is the number of rows and n is the number of columns. We may visit every pixel once.
Space Complexity / 空间复杂度: O(m * n) in the worst case due to the recursion stack or queue for DFS and BFS, respectively.

Key Concept / 关键概念

Flood Fill / 洪水填充: This technique involves exploring and modifying connected regions in a grid, commonly used in image processing and graph traversal.
洪水填充: 这种技术涉及在网格中探索和修改连接区域，通常用于图像处理和图遍历。

Summary / 总结

English: Flood fill can be efficiently implemented using either DFS or BFS, depending on the constraints and size of the grid. Understanding both methods allows for flexible problem-solving.
Chinese: 洪水填充可以使用 DFS 或 BFS 来高效实现，具体取决于网格的约束和大小。理解这两种方法可以灵活地解决问题。

Tips / 提示

English: Practice implementing both DFS and BFS to understand their trade-offs in different scenarios, such as when dealing with deep vs. wide grids.
Chinese: 练习实现 DFS 和 BFS，以理解它们在不同场景中的权衡，例如在处理深网格与宽网格时。

Solution Template for Similar Questions / 提示

English: Use DFS or BFS when you need to explore or modify connected components in a grid, especially in problems related to image processing or graph traversal.
Chinese: 当你需要在网格中探索或修改连接组件时，使用 DFS 或 BFS，特别是在与图像处理或图遍历相关的问题中。

5 More Similar Questions / 推荐5问题

Code 130. Surrounded Regions](https://leetcode.com/problems/surrounded-regions/)

LeetCode 785. Is Graph Bipartite?

Recommended Resources / 推荐资源

English: Practice problems that involve DFS or BFS to deepen your understanding of these traversal techniques in different grid-based contexts.
Chinese: 练习涉及 DFS 或 BFS 的问题，以加深你对这些遍历技术在不同网格背景中的理解。

Post Views: 18

CODEBITWAVE