Easy

题目描述

有一幅以 m x n 的二维整数数组表示的图画 image，其中 image[i][j] 表示该图画的像素值大小。

你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。

为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这些像素点与初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，……，直到没有更多的记录像素点为止。将所有有记录的像素点的颜色值改为 newColor 。

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

示例 1:

输入: 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]]
解析: 
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

示例 2:

输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 0
输出: [[0,0,0],[0,0,0]]
解析: 
初始像素的颜色已经是目标颜色了，所以不会有任何改变。

提示:

  • m == image.length
  • n == image[i].length
  • 1 <= m, n <= 50
  • 0 <= image[i][j], newColor < 2^16
  • 0 <= sr < m
  • 0 <= sc < n

解题思路

这道题是经典的图像填充问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。

解题思路：

  1. 核心思想：从起始像素开始，将所有与起始像素颜色相同且连通的像素点都染成新颜色。

  2. 边界条件处理：首先检查起始像素的颜色是否已经是目标颜色，如果是则无需改变直接返回原图像。

  3. DFS递归方法（推荐）：

    • 记录起始像素的原始颜色
    • 从起始位置开始递归搜索
    • 对于每个像素，检查是否在边界内且颜色与原始颜色相同
    • 如果满足条件，将像素染色并递归处理四个方向的邻居

  4. BFS迭代方法：

    • 使用队列存储待处理的像素坐标
    • 逐层处理相邻的同色像素

  5. 关键优化：当新颜色与原始颜色相同时直接返回，避免无限递归。

两种方法的时间复杂度相同，但DFS实现更简洁。需要注意的是要先判断新颜色是否与原颜色相同，这是防止栈溢出的重要优化。

代码实现

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) return image;
        
        dfs(image, sr, sc, originalColor, color);
        return image;
    }
    
private:
    void dfs(vector<vector<int>>& image, int x, int y, int originalColor, int newColor) {
        if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || 
            image[x][y] != originalColor) {
            return;
        }
        
        image[x][y] = newColor;
        
        dfs(image, x + 1, y, originalColor, newColor);
        dfs(image, x - 1, y, originalColor, newColor);
        dfs(image, x, y + 1, originalColor, newColor);
        dfs(image, x, y - 1, originalColor, newColor);
    }
};

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(x, y):
            if (x < 0 or x >= len(image) or y < 0 or y >= len(image[0]) or 
                image[x][y] != original_color):
                return
            
            image[x][y] = color
            
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)
        
        dfs(sr, sc)
        return image

public class Solution {
    public int[][] FloodFill(int[][] image, int sr, int sc, int color) {
        int originalColor = image[sr][sc];
        if (originalColor == color) return image;
        
        DFS(image, sr, sc, originalColor, color);
        return image;
    }
    
    private void DFS(int[][] image, int x, int y, int originalColor, int newColor) {
        if (x < 0 || x >= image.Length || y < 0 || y >= image[0].Length || 
            image[x][y] != originalColor) {
            return;
        }
        
        image[x][y] = newColor;
        
        DFS(image, x + 1, y, originalColor, newColor);
        DFS(image, x - 1, y, originalColor, newColor);
        DFS(image, x, y + 1, originalColor, newColor);
        DFS(image, x, y - 1, originalColor, newColor);
    }
}

var floodFill = function(image, sr, sc, color) {
    const originalColor = image[sr][sc];
    
    if (originalColor === color) return image;
    
    const dfs = (r, c) => {
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] !== originalColor) {
            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;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)最坏情况下需要访问图像中的每个像素点一次，其中 m 和 n 分别是图像的行数和列数
空间复杂度O(m × n)递归调用栈的深度最坏情况下为 m × n（当所有像素都需要填充时形成一条链）

相关题目