0% completed

Solution: Flood Fill

Problem Statement

Any image can be represented by a 2D integer array (i.e., a matrix) where each cell represents the pixel value of the image.

Flood fill algorithm takes a starting cell (i.e., a pixel) and a color. The given color is applied to all horizontally and vertically connected cells with the same color as that of the starting cell. Recursively, the algorithm fills cells with the new color until it encounters a cell with a different color than the starting cell.

Given a matrix, a starting cell, and a color, flood fill the matrix.

Example 1:

Input: matrix =

starting cell

.....

Like the course? Get enrolled and start learning!

M

Mitch

· 4 years ago

Show 4 replies

Elaine Michelle Teh

· 4 years ago

Show 3 replies

T

Thai Minh

· 3 years ago

from collections import deque
class Solution:
  def floodFill(self, matrix, x, y, newColor):
    # TODO: Write your code here
    # BFS solution, we can use visited to mark the visited cell then rewrite it with color
    # for row in range(len(matrix)):
    #   for col in range(len(matrix[0])):
    # self.visitCellBFS(matrix, x, y, newColor)
    self.visitCellDFS(x, y, matrix, matrix[x][y], newColor)
    return matrix
  def visitCellBFS(self, matrix, row, col, newColor):
    neighbors = deque([(row, col)])
    oldColor = matrix[row][col]
    visited_list = [[False for _ in range(len(matrix[0]))] for _ in range(len(matrix))]

    while neighbors:
      row, col = neighbors.popleft()

      if row < 0 or row >= len(matrix) or col < 0 or col >= len(matrix[0]):
        continue

Luis Roel

· 3 years ago

class Solution:
  def floodFill(self, matrix, x, y, newColor):
    startingColor = matrix[x][y]
    seen = set()

    def go(x, y):
      if (x, y) in seen:
        return
      
      if x < 0 or x >= len(matrix):
        return
      if y < 0 or y >= len(matrix[0]):
        return
      
      seen.add((x, y))

      if matrix[x][y] != startingColor:
        return

      matrix[x][y] = newColor

      go(x + 1, y)
      go(x - 1, y)
      go(x, y + 1)
      go(x, y - 1)

    go(x, y)
    
    return matrix