733. Flood Fill

https://leetcode.com/problems/flood-fill/

Python

DFS

DFS with memory to prevent duplicate visiting

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        origin_color = image[sr][sc]
        row_limit = len(image) - 1
        col_limit = len(image[0]) - 1

        seem = set()

        if origin_color == newColor:
            return image

        def dfs(row, col):
            if (row, col) in seem:
                return

            if image[row][col] == origin_color:
                image[row][col] = newColor
                seem.add((row, col))
                if row >= 1:
                    dfs(row-1, col)
                if row + 1 <= row_limit:
                    dfs(row+1, col)
                if col - 1 >= 0:
                    dfs(row, col-1)
                if col + 1 <= col_limit:
                    dfs(row, col+1)

        dfs(sr, sc)
        return image

BFS

from collections import deque

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        row_limit = len(image) - 1
        col_limit = len(image[0]) - 1
        origin_color = image[sr][sc]

        queue = deque([(sr, sc)])

        seem = set()

        while queue:
            row, col = queue.popleft()
            if (row, col) in seem:
                continue

            if image[row][col] == origin_color:
                image[row][col] = newColor
                seem.add((row, col))
                if row >= 1:
                    queue.append((row-1, col))
                if row + 1 <= row_limit:
                    queue.append((row+1, col))
                if col - 1 >= 0:
                    queue.append((row, col-1))
                if col + 1 <= col_limit:
                    queue.append((row, col+1))
        return image