733.md

733. Flood Filln

Solution 1 (time O(mn), space O(mn))

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]]
        """
        if newColor == image[sr][sc]:
            return image
        m, n = len(image), len(image[0])
        q = deque([(sr, sc)])
        oldColor = image[sr][sc]
        image[sr][sc] = newColor
        while q:
            cur_x, cur_y = q.popleft()
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                new_x = cur_x + dx
                new_y = cur_y + dy
                if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n:
                    continue
                if image[new_x][new_y] == oldColor:
                    image[new_x][new_y] = newColor
                    q.append((new_x, new_y))
        return image