Leetcode 733.图像渲染

Posted on |

733. 图像渲染

题目

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

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

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

1
2
3
4
5
6
7
8
9
10
11
示例 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。
image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。

方法

方法1：深度优先搜索

在开始结点执行DFS，然后继续执行DFS，如果：

  • 下一个结点在边界范围内
  • 下一个结点的颜色和原始结点的初始颜色相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        R,C,originColor=len(image),len(image[0]),image[sr][sc]

        def traverse(row,col):
            if not (0<=row<R  and 0<=col<C) or image[row][col]!=originColor:
                return
            image[row][col]=newColor
            [traverse(row+x,col+y) for (x,y) in ((0,1),(0,-1),(1,0),(-1,0))]

        if originColor!=newColor:
            traverse(sr,sc)

        return image
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        oldColor,m,n=image[sr][sc],len(image),len(image[0])

        def dfs(i,j):
            image[i][j]=newColor

            # for x,y in ((1,0),(-1,0),(0,1),(0,-1)):
            #     if 0<=i+x<m and 0<=j+y<n and image[i+x][j+y]==oldColor:
            #         dfs(i+x,j+y)
            for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                if 0<=x<m and 0<=y<n and image[x][y]==oldColor:
                    dfs(x,y)

        if oldColor!=newColor:
            dfs(sr,sc)
        return image

方法2：广度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        """
        :type image: List[List[int]]
        :type sr: int
        :type sc: int
        :type newColor: int
        :rtype: List[List[int]]
        """
        oldColor,m,n=image[sr][sc],len(image),len(image[0])
        if oldColor!=newColor:
            queue=collections.deque([(sr,sc)])
            while queue:
                i,j=queue.popleft()
                image[i][j]=newColor
                for x,y in ((i-1,j),(i+1,j),(i,j+1),(i,j-1)):
                    if 0<=x<m and 0<=y<n and image[x][y]==oldColor:
                        queue.append((x,y))
        return image