733. 图像渲染

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/flood-fill

题目

有一幅以二维整数数组示意的图画，每一个整数示意该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (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，因为它不是在上下左右四个方向上与初始点相连的像素点。

留神:

• image 和 image[0] 的长度在范畴 [1, 50] 内。
• 给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
• imagei 和 newColor 示意的色彩值在范畴 [0, 65535]内。

解题思路

思路：DFS、BFS

先审题，题目要求是将某些符合条件的坐标点进行从新上色。这里这些坐标点合乎的定义为：间接或间接相邻的与起始坐标点色彩雷同的局部。

在题目中，明确说了从给定的初始坐标开始，往坐标点四个方位进行扩散，标记与初始坐标点色彩雷同的坐标，而后以这些标记的点持续扩散，反复直至完结，将所有标记的点都从新上色。

那么，咱们这里采纳深度优先搜寻和广度优先搜寻的模式来解决这个问题。

深度优先搜寻（DFS）

首先，先看深度优先搜寻如何解决。具体的做法如下：

• 首先从给定的初始坐标点开始向四个方位扩散，进行遍历；
• 每搜寻一个坐标，确定是否与初始坐标点色彩雷同。如果雷同，那么从新上色，避免从新搜寻陷入死循环；如果不同，不解决。
• 反复直至所有符合条件的点都从新上色，返回从新上色后的图像。

这里有个须要留神的中央，进行扩散的时候，依照下面的做法，会将初始坐标点进行从新上色。这个时候色彩的变动会影响后续。所以开始前用一个遍历存储初始坐标点的色彩。
还有，给定的初始坐标点色彩，可能与新给定的色彩雷同，这样间接调用会先入死循环。这也是测试用例没通过留神到的。┑(￣ ￣)┍

具体的代码见【代码实现 # 深度优先搜寻】

广度优先搜寻（BFS）

在这里，咱们同样能够应用广度优先搜寻的思路来解决这个问题。上面看应用此办法的思路：

• 申明辅助队列，从初始坐标点开始，先将初始坐标点入队；
• 出队，开始搜寻，当遇到与初始坐标点色彩雷同的点时，入队，同时将从新上色；
• 循环直至队列为空，返回从新上色后的图像。

同样留神初始坐标点色彩可能会被笼罩的问题。

具体的代码见【代码实现 # 广度优先搜寻】

代码实现

# 深度优先搜寻class Solution:    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:        # 先存储初始坐标点色彩        init_color = image[sr][sc]        # 边界        m = len(image)        n = len(image[0])        # 四个方位        directions = [(0, 1), (0, -1), (-1, 0),(1, 0)]        def dfs(x, y):            """进行深度优先搜寻            Args:                x: 像素值（行）                y: 像素值（列）            """            if image[x][y] == init_color:                # 如果遇到与初始坐标点色彩雷同的点，从新上色，开始扩散                image[x][y] = newColor                for dx, dy in directions:                    nx = x + dx                    ny = y + dy                    # 限定边界                    if 0 <= nx < m and 0 <= ny < n and image[nx][ny] == init_color:                        dfs(nx, ny)        # 留神:        # 有可能一开始给定的初始坐标点的色彩与前面给定的新色彩是雷同的        # 间接调用会先入死循环，直至超出递归深度        if init_color != newColor:            dfs(sr, sc)        return image# 广度优先搜寻class Solution:    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:        # 先存储初始坐标点色彩        init_color = image[sr][sc]        # 边界        m = len(image)        n = len(image[0])        # 四个方位        directions = [(0, 1), (0, -1), (-1, 0),(1, 0)]        def bfs(sr, sc):            """进行深度优先搜寻            Args:                sr: 像素值（行）                sc: 像素值（列）            """            # 申明辅助队列            from collections import deque            queue = deque()            # 入队            queue.append([sr, sc])            # 从新上色            image[sr][sc] = newColor            # 出队，开始搜寻            while queue:                x, y = queue.popleft()                for dx, dy in directions:                    nx = x + dx                    ny = y + dy                    if 0 <= nx < m and 0 <= ny < n and image[nx][ny] == init_color:                        # 当遇到与初始坐标点色彩雷同的，入队，并从新上色                        queue.append([nx, ny])                        image[nx][ny] = newColor        if init_color != newColor:            bfs(sr, sc)        return image

实现后果

欢送关注

公众号 【书所集录】