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