1. 题目描述

有一幅以?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 = 2
输出: [[2,2,2],[2,2,2]]

提示:

m == image.length
n == image[i].length
1 <= m, n <= 50
0 <= image[i][j], newColor < 216
0 <= sr <?m
0 <= sc <?n

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flood-fill
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

????????把整幅图像看作是一个图（Graph, instead of picture）从起点开始，采用广度优先搜索的方式对整个。

? ? ? ? 每个像素为一个节点，其邻接点即为其上下左右邻接的像素点（除了已经访问过的以外）。这里要注意的是，这个Graph并不是已经存在，而是在遍历的过程中构建出来。

? ? ? ? 需要visited记录已经访问过的节点（像素），由于并不需要跟踪深度、或者层数、或者最短路径之类的信息，单纯地就是记录是否访问过，所以可以用set来实现visited（set和dict都是哈希方式，查询效率相当）。? ? ? ?

????????

? ? ? ? 【复杂度分析】

????????时间复杂度：O(n×m)，其中 n 和 m 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。

????????空间复杂度：O(n×m)，其中 n 和 m 分别是二维数组的行数和列数。主要为队列的开销。

3. 代码实现

from typing import List
from collections import deque
class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        R,C = len(image),len(image[0])
        q = deque()
        visited = set()        
        q.append((sr,sc))
        visited.add((sr,sc))
        
        while len(q) > 0:
            pr,pc = q.popleft()
            
            if pr-1>=0 and image[pr-1][pc]==image[pr][pc] and (pr-1,pc) not in visited:
                q.append((pr-1,pc))
                visited.add((pr-1,pc))

            if pr+1<R and image[pr+1][pc]==image[pr][pc] and (pr+1,pc) not in visited:
                q.append((pr+1,pc))
                visited.add((pr+1,pc))

            if pc-1>=0 and image[pr][pc-1]==image[pr][pc] and (pr,pc-1) not in visited:
                q.append((pr,pc-1))
                visited.add((pr,pc-1))
            
            if pc+1<C and image[pr][pc+1]==image[pr][pc] and (pr,pc+1) not in visited:
                q.append((pr,pc+1))
                visited.add((pr,pc+1))
            
            image[pr][pc] = newColor
        return image
            
        
if __name__ == '__main__':
    sln = Solution()
    
    image = [[1,1,1],[1,1,0],[1,0,1]]
    sr = 1
    sc = 1
    newColor = 2
    print(sln.floodFill(image, sr, sc, newColor))
    
    image = [[0,0,0],[0,0,0]]
    sr = 0
    sc = 0
    newColor = 2
    print(sln.floodFill(image, sr, sc, newColor))

????????执行用时：44 ms, 在所有?Python3?提交中击败了28.41%的用户

????????内存消耗：15.2 MB, 在所有?Python3?提交中击败了21.47%的用户

????????虽然性能有点拉跨但是好歹是一次性通过的。??

? ? ? ? 以上代码有点冗长，主要是边界判断比较麻烦。实际上这一类问题的通常的简化边界判断的做法是外面加一层围栏，围栏中的值填入对于image而言的非法值，这样代码中分别用于上下左右判断的4个if...语句块可以用一个for-loop来表现。

? ? ? ? 另外一个可以改进的地方是，可以省掉visited。因为已经访问过的像素就已经被设成新的颜色了。而且，如果起始点的当前颜色与newColor相同的话，就不需要任何操作直接返回即可。

? ? ? ? 由于是图的遍历，本题也可以用深度优先搜索来解决。

? ? ? ? 回到主目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)