leetcode回顾——Flood Fill

LeetCode

题目

“””
An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor,
“flood fill” the image.

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 the newColor.

At the end, return the modified image.

Example 1:
Input:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation:
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.
“””

用过ps的人应该都熟悉一个功能，就是颜色填充；而这道题目的意思，其实就像颜色填充一样，把一个区域的oldColor用newColor代替，因此，这里就涉及到了如何识别一个区域？

洪水填充算法

洪水会向四周能够流动的地方流动，因此我们就可以模范洪水的流动方式：在某个点，对这个点的四个方向进行可流动性判断，如果是可流动的，那么就流过去，否则不流，其实就是判断这个点的四个方向上的点与当前的点是不是属于同一块区域，然后进行替换操作；当四个方向都执行完之后，就采用深度优先搜索向下一个点出发，继续之前的操作，直到所有需要被替换的区域都已经被替换成新的信息位置

注意点

由于DFS是递归运行的，所以可能会出现由于递归的深度过深导致栈爆炸，因此需要利用python中的sys模块，进行如下设置

1
2
sys.setrecursionlimit(100000)
(设置递归的深度)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import sys

sys.setrecursionlimit(1000000)


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]]
        """
        wight, length = len(image), len(image[0])
        oldColor = image[sr][sc]
        for i in range(wight):
            for j in range(length):
                if image[i][j] == oldColor and image[i][j] != newColor:
                    self.DFS(image, newColor, sr, sc, oldColor)
        return image

    def DFS(self, image, newColor, i, j, oldColor):
        if i < 0 or i >= len(image):
            return
        if j < 0 or j >= len(image[0]):
            return
        if image[i][j] != oldColor:
            return
        image[i][j] = newColor

        def fill_color(_image, _i, _j):
            if _i < 0 or _i >= len(image):
                return
            if _j < 0 or _j >= len(image[0]):
                return
            if _image[i][j] != oldColor:
                return
            _image[i][j] = newColor

        fill_color(image, i, j + 1)
        fill_color(image, i, j - 1)
        fill_color(image, i + 1, j)
        fill_color(image, i - 1, j)
        self.DFS(image, newColor, i, j + 1, oldColor)
        self.DFS(image, newColor, i, j - 1, oldColor)
        self.DFS(image, newColor, i + 1, j, oldColor)
        self.DFS(image, newColor, i - 1, j, oldColor)


if __name__ == '__main__':
    s = Solution()
    image = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
    sr = 1
    sc = 1
    newColor = 2
    print s.floodFill(image, sr, sc, newColor)