from collections import deque

class Solution:
  def countClosedIslands(self, matrix):
    countClosedIslands = 0
    # TODO: Write your code here
    # during the visit, we want to check if any node of island reside on the edge, then force return 0 if it is
    # Time complexity: O(row * col)
    # Space complexity: O(row * col) 
    for row in range(len(matrix)):
      for col in range(len(matrix[0])):
        if matrix[row][col] == 1:
          countClosedIslands += self.visitIsland(row, col, matrix)
    return countClosedIslands
  def visitIsland(self, row, col, matrix):
    num_return = 1
    neighbors = deque([(row, col)])
    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] == 0:
        continue
      
      matrix[row][col] = 0

      if (row == 0 and col <= len(matrix[0]) - 1) or \
      (row == len(matrix) - 1 and col <= len(matrix[0]) - 1) or \
      (col == 0 and row <= len(matrix) - 1) or \
      (col == len(matrix[0]) - 1 and row <= len(matrix) - 1): 
        num_return = 0
      neighbors.extend([(row + 1, col)])
      neighbors.extend([(row - 1, col)])
      neighbors.extend([(row, col - 1)])
      neighbors.extend([(row, col + 1)])

    return num_return