1254.md

1254. Number of Closed Islands

Solution 1 (time O(mn), space O(mn))

# BFS
class Solution(object):
    def closedIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    q = deque([(i, j)])
                    grid[i][j] = 1
                    flag = True
                    while q:
                        x, y = q.popleft()
                        if x == 0 or y == 0 or x == m - 1 or y == n - 1:
                            flag = False
                        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                            new_x = x + dx
                            new_y = y + dy
                            if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == 0:
                                grid[new_x][new_y] = 1
                                q.append((new_x, new_y))
                    if flag:
                        ans += 1
        return ans