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
      
      if matrix[row][col] != oldColor or visited_list[row][col]:
        continue
      
      visited_list[row][col] = True
      matrix[row][col] = newColor

      neighbors.extend([(row - 1, col)])
      neighbors.extend([(row + 1, col)])
      neighbors.extend([(row, col + 1)])
      neighbors.extend([(row, col - 1)])


  def visitCellDFS(self, row, col, matrix, oldColor, newColor):
    # return case where it is not valid cell (out of bound)
    if row < 0 or row >= len(matrix) or col < 0 or col >= len(matrix[0]):
      return 
      
    # return if it is not the same color as root cell
    if matrix[row][col] != oldColor:
      return

    # remark this cell with new color
    matrix[row][col] = newColor

    # recursive call all adjacent cells
    self.visitCellDFS(row + 1, col, matrix, oldColor, newColor)
    self.visitCellDFS(row - 1, col, matrix, oldColor, newColor)
    self.visitCellDFS(row, col - 1, matrix, oldColor, newColor)
    self.visitCellDFS(row, col + 1, matrix, oldColor, newColor)