题目

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

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

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

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

示例 1:

1
2
3
4
5
6
7
8
9

输入: 
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]内。

DFS 与 BFS 两种方法 三种实现 超精简代码 趣味详解

这道题建议和“岛屿数量”一题一起看，先做这道再做岛屿数量，双倍的收获，双倍的快乐(ゝ∀･)

BFS

BFS，即广度优先搜索。

有的小朋友就问了：“哥哥哥哥，我就是想画画，你能不能讲人话？”
说人话就是，我们按照这个步骤来做——

思路

• 首先找到初始节点，给它染色，这个初始节点当作第一层。
• 找到初始节点周围四个节点，给它们染色（符合条件的才能染），这四个节点当作第二层。
• 再找到这四个节点周围八个节点，给它们染色，这八个节点当作第三层。
• 重复以往，层层递进，直到找不到符合要求的节点。

思路很好理解对吧，就是一个从中间向外扩散的过程。可是怎么实现呢？现在给您键盘，恐怕还写不出。

实现

这里就要介绍一下队列，因为广度优先搜索和队列是好基友。
什么是队列？就是一个先进先出的数组，和我们日常生活中的排队很像。当我们向队列插入一个新数的时候，它插在最后，当我们取出一个数的时候，要从头取。就像小朋友刚刚买的画笔或者画板或者颜料，都是要排队的（假设没有网购，不许杠！）。

补充——关于在Python中使用队列
在 Python 中，可以使用以下几种方法实现队列

• collections包里的deque，对应操作
  • pop()从尾取出
  • appendleft() 从头插入
• queue包中的queue，对应操作
  • put() 插入
  • get() 取出
• 直接使用list，只要保证只使用
  • pop() 取出
  • insert(0,) 插入
    或者只使用
  • append() 插入
  • list[0]并且del list[0] 取出
    两者使用list方法的不同就区别于你把哪个当头，哪个当尾

三种方法各有优劣。

• 第一种是正统的Python的双端队列，缺点是调用的函数有点复杂，可能一不小心写了append，就不对了。
• 第二种使用封装的函数很直接，put()和get()不容易搞混淆。但是queue类型其实里面本身就装了一个deque，有点脱裤子放X的感觉。
• 第三种优势在于不用调包，但是函数使用逻辑可能造成混淆。在
  这里，完整版代码采用第二种，好理解，精简版代码采用第三种，省行数。三种方式可以按照你的喜好互相替换，完全不影响结果。

这时候小朋友又问了：“叔叔叔叔，为什么广度优先搜索和队列能勾搭到一块儿？”

我们可以这样利用队列实现广度优先搜索。

• 我们设置一个队列，先把初始点添加进去
• 规定每次从队列取出一个坐标
• 对这个坐标染色，并且把这个坐标的邻居（符合要求且不重复的好邻居），放到队列中。
• 当这个队列为空的时候，说明染色完成

因为队列每次取出的是最后的，而每次添加的是放在最前面，所以可以想象到，每次先处理的都是层级最少的，最接近初始点的，然后慢慢扩大，这样就实现了广度优先搜索。

这时候小朋友很好奇：“爷爷爷爷，这个层级顺序有那么重要吗？”

在这道题目里，层级是不重要的，这也是为什么后来还有个深度优先搜索，也可以解决这道题目。但是广度优先搜索的特点就在于这个层级，在很多题目当中它是很重要的。有时候，对队列取出元素的时候，要设置循环，固定住当前的队列项，对当前的队列项操作——因为当前的队列项一定是相同层级的。例如，在我们寻找到达某个节点的最小步数的时候，层级也就是步数就显得尤为重要了。在leetcode当中，有很多题都是需要广度优先搜索的，这是一种解题的思想，要熟练掌握。而实现这个思想，又离不开队列。两者相辅相成。

小朋友“啪”地一下打翻了颜料瓶：“糟老头子整这些有的没的，给我写！”

哎等等，容我说最后一句
在这道题目当中，要注意起始颜色和目标颜色一定要不同，不然会死循环！

代码

首先来看完整注释详细版：

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

from queue import Queue

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        # 起始颜色和目标颜色相同，则直接返回原图
        if newColor == image[sr][sc]:
            return image
        # 设置四个方向偏移量，一种常见的省事儿技巧
        directions = {(1, 0), (-1, 0), (0, 1), (0, -1)}
        # 构造一个队列，先把起始点放进去
        que = Queue()
        que.put((sr, sc))
        # 记录初始颜色
        originalcolor = image[sr][sc]
        # 当队列不为空                              
        while not que.empty():
            # 取出队列的点并染色
            point = que.get()
            image[point[0]][point[1]] = newColor
            # 遍历四个方向
            for direction in directions:
                # 新点是(new_i,new_j)
                new_i = point[0] + direction[0]
                new_j = point[1] + direction[1]
                # 如果这个点在定义域内并且它和原来的颜色相同
                if 0 <= new_i < len(image) and 0 <= new_j < len(image[0]) and image[new_i][new_j] == originalcolor:
                    que.put((new_i, new_j))
        return image

别看它太长，其实都是注释。这还有个精简版，把遍历改成了使用zip，只有九行哦——

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        if newColor == image[sr][sc]:return image
        que, old,  = [(sr, sc)], image[sr][sc]
        while que:
            point = que.pop()
            image[point[0]][point[1]] = newColor
            for new_i, new_j in zip((point[0], point[0], point[0] + 1, point[0] - 1), (point[1] + 1, point[1] - 1, point[1], point[1])): 
                if 0 <= new_i < len(image) and 0 <= new_j < len(image[0]) and image[new_i][new_j] == old:  
                    que.insert(0,(new_i,new_j))
        return image

DFS

DFS，即深度优先搜索。

小朋友抢着说：“从你的BFS里，我好想猜到了DFS是什么了，它是不是——”

思路

• 先定个四个方向的顺序，例如上下左右，先上后下后左最后右
• 首先找到初始节点，给它染色。
• 按照方向的顺序，这里是上，就先把这个点的上方点先染色。
• 一直往上一直往上，直到不符合要求，便退一步，再找这个点的下方向
• 重复这个步骤。

换句话说，先把这个点上方的都弄完，再把这个点下边的都弄完，再左边的，最后下边的。

思路很好理解对吧，就是一个从中间向一个方向深入的过程。可是怎么实现呢？现在给您键盘，恐怕还写不出。

实现

还记得标题写的两个方法，三种实现吗？
这是因为 DFS 通常有两种实现方法，一种是递归，另一种是使用栈。
这里就要介绍一下栈，因为深度优先搜索和栈是好基友。
什么是栈？就是一个后进先出的数组，和我们日常生活中的插队很像。当我们向栈插入一个新数的时候，它插在最前面，当我们取出一个数的时候，要从头取。就像小朋友插队去买画笔，他不排队，直接插到第一个位置，下一个服务的就是它。

补充——关于在Python中使用栈
直接使用list即可，使用它的这两个方法

• pop()
• append()

这时候小朋友又问了：“叔叔叔叔，为什么广度优先搜索和堆栈能勾搭到一块儿？”

我们可以这样利用堆栈实现深度优先搜索。

• 我们设置一个栈，先把初始点添加进去
• 规定每次从栈中取出一个坐标
• 对这个坐标染色，并且把这个坐标的一个方向上的邻居（符合要求且不重复的好邻居），放到栈中。
• 当这个方向没有复合要求的邻居的时候，进入下一个方向
• 当这个栈为空的时候，说明染色完成

因为栈每次取出的是最后的，而每次添加的也在最后，所以可以想象到，每次先处理的都是最深的，然后慢慢扩大，这样就实现了深度优先搜索。

这时候小朋友很好奇：“爷爷爷爷，这个深度顺序有那么重要吗？”

在这道题目里，层级是不重要的，这也是为什么前面还有个广度优先搜索，也可以解决这道题目。在leetcode当中，有很多题都是需要深度优先搜索的，这是一种解题的思想，要熟练掌握。而实现这个思想，又离不开栈，递归。两者相辅相成。

小朋友“啪”地一下打翻了颜料瓶：“糟老头子整这些有的没的，给我写！”

哎等等，容我说最后一句
在这道题目当中，要注意起始颜色和目标颜色一定要不同，不然会死循环！

代码一：使用栈

因为和之前BFS其实差不多，所以只放精简版了。

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        if newColor == image[sr][sc]: return image
        stack, old = [(sr, sc)], image[sr][sc]
        while stack:
            point = stack.pop()
            image[point[0]][point[1]] = newColor
            for new_i, new_j in zip((point[0], point[0], point[0] + 1, point[0] - 1), (point[1] + 1, point[1] - 1, point[1], point[1])): 
                if 0 <= new_i < len(image) and 0 <= new_j < len(image[0]) and image[new_i][new_j] == old:
                    stack.append((new_i, new_j))
        return image

代码二：使用递归

这里参考了 knife 的题解
可以看到，和使用栈的方法其实差不多

1
2
3
4
5
6
7
8

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        if image[sr][sc] != newColor:
            old, image[sr][sc] = image[sr][sc], newColor
            for i, j in zip((sr, sr+1, sr, sr-1), (sc+1, sc, sc-1, sc)):
                if 0 <= i < len(image) and 0 <= j < len(image[0]) and image[i][j] == old:
                    self.floodFill(image, i, j, newColor)
        return image

补充

• 接下来建议去做岛屿数量这一题
• 岛屿数量会更难，原因在于两点
  • 需要增加一个哈希表来判断相应节点是否已经被处理过，不能像我们这样靠颜色一把梭
  • 需要记录岛屿数量，即再多一个外循环，处理好count。

小朋友高兴地作画了，你也快高兴地做题吧！Good Luck!