leetcode 733. 图像渲染 python

题目描述：

题解 ：

从给定的坐标[sr,sc]开始，判断其上下左右四个位置原来的颜色是否与[sr,sc]相同，相同则将其染成新的颜色，然后再以该位置为起点，判断其周围四个位置。可以采用深度优先和广度优先梁总方法。

参考：​​​​​​https://segmentfault.com/a/1190000023648280

题解一：深度优先搜索

如果image[sr,sc]值和newColor相等，则不用做任何处理。
1.将给定位置的初始颜色记录为oricolor，防止之后被更改为newColor。
2.定义dfs函数，对位置[i,j]进行处理，首先判断image[i][j]是否和oricolor相等，相等则将其修改为newColor，然后分别对它上下左右四个位置调用dfs函数。
class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        if image[sr][sc]==newColor:
            return image
        direction = [(0,-1),(0,1),(-1,0),(1,0)]
        oricolor = image[sr][sc]
        def dfs(i,j):
            if image[i][j] == oricolor:
                image[i][j] = newColor
                for dx,dy in direction:
                    x = i+dx
                    y = j+dy
                    if 0<=x 
 
 题解二：广度优先搜索
 
使用一个队列实现：
 
定义一个bfs函数，需要染色的位置为[posx,posy]
 
1.定义一个队列myq，将[posx,posy]加入队列。
 
2.每次从队列中取出一个元素[x,y]，将image[x][y]更新为newColor，然后将该位置的上下左右位置加入队列（需要进行边界判断以及位置的初始颜色是否与oricolor相同）
 
class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        if image[sr][sc] == newColor:
            return image
        oricolor = image[sr][sc]
        direction = [(-1,0),(1,0),(0,-1),(0,1)]
        def bfs(posx,posy):
            myq = deque()
            myq.append([posx,posy])
            while myq:
                x,y = myq.popleft()
                image[x][y] = newColor
                for dx,dy in direction:
                    nx = x+dx
                    ny = y+dy
                    if 0<=nx 
 
 
 广度优先和深度优先的方法都是从位置[x,y]开始，对其上下左右四个位置进行判断，然后再处理这四个相邻位置的相邻位置。
 
区别在于，深度优先搜索中，获得一个[x,y]的相邻位置后，马上以该位置作为中心，对它的相邻位置进行处理，这个相邻位置处理完成后，再处理下一个相邻节点。
 
广度优先搜索中，先处理完当前节点的全部四个相邻位置之后，再以这些相邻节点为中心向外处理。