Given a 2D grid consists of 0s (land) and 1s (water).  An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.
Return the number of closed islands.
 
Example 1:

Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).
Example 2:

Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1

Example 3:
Input: grid = [[1,1,1,1,1,1,1],
               [1,0,0,0,0,0,1],
               [1,0,1,1,1,0,1],
               [1,0,1,0,1,0,1],
               [1,0,1,1,1,0,1],
               [1,0,0,0,0,0,1],
               [1,1,1,1,1,1,1]]
Output: 2

 
Constraints:

1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1

Difficulty: interview

Starter code:

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        count = 0 
        for i in range(1,len(grid)-1):
            for j in range(1,len(grid[0])-1):
                if grid[i][j] ==0 and self.dfs(grid,i,j):
                    count+=1
        return count 
    def dfs(self,grid,i,j):
        if grid[i][j]==1:
            return True
        if i<=0 or j<=0 or i>=len(grid)-1 or j>= len(grid[0])-1:
            return False
        grid[i][j]=1
        up= self.dfs(grid,i+1,j)
        down= self.dfs(grid,i-1,j)
        left= self.dfs(grid,i,j-1)
        right= self.dfs(grid,i,j+1)
        return up and down and left and right

class Solution:
    LAND = 0
    WATER = 1
    def closedIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        count=0
        m, n, count = len(grid), len(grid[0]) if grid else 0, 0           
        for i in range(1, len(grid)-1):
            for j in range(1, len(grid[0])-1):
                if grid[i][j]==self.LAND and self.dfs(i,j,grid) :
                    count +=1
        return count
    def inside_grid(self,x, y,grid):
        return 0 <= x < len(grid) and 0 <= y < len(grid[0])
    
    def dfs(self,i,j,grid):
        #m, n = len(grid), len(grid[0]) if grid else 0       
        #Test = True
        if grid[i][j]==self.WATER:
            Test = True
            return True
        
        if(i<=0 or j<=0 or j>= len(grid[0])-1 or i >= len(grid)-1):
            Test = False
            return False
        grid[i][j] = self.WATER 
        Test= True & self.dfs(i+1,j,grid)
        Test= Test& self.dfs(i-1,j,grid)
        Test= Test& self.dfs(i,j+1,grid)
        Test= Test& self.dfs(i,j-1,grid)
        return Test  

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        self.num_closed_islands = 0
        self.visited = set()
        self.grid = grid
        self.m = len(grid)
        self.n = len(grid[0])
        for i in range(1, self.m - 1):
            for j in range(1, self.n - 1):
                if grid[i][j] == 0 and (i, j) not in self.visited:
                    self.include = True
                    self.dfs(i, j)
                    if self.include:
                        self.num_closed_islands += 1
        return self.num_closed_islands

    def dfs(self, i, j):
        if i == 0 or j == 0 or i == (self.m - 1) or j == (self.n - 1):
            self.include = False
        self.visited.add((i, j))
        for x, y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            next_i, next_j = i + x , j + y
            if (self.in_range(next_i, next_j) and 
                (next_i, next_j) not in self.visited and 
                self.grid[next_i][next_j] == 0):
                self.dfs(next_i, next_j)
\t\t
    def in_range(self, i, j):
        return  0 <= i < self.m and 0 <= j < self.n


class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        self.grid = grid
        self.visited = [ [ 0 for _ in range(len(grid[0])) ] for _ in range(len(grid))]
        def dfs(i, j):
            if i < 0 or j < 0 or i>=len(self.grid) or j>=len(self.grid[0]) :
                return False
            if self.grid[i][j] == 1 or self.visited[i][j]==1:
                return True
            self.visited[i][j] = 1
            neighbs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
            ans = True
            for x, y in neighbs:
                curr = dfs(i+x, j+y)
                if curr == False:
                    ans = False
            return ans
        
        ans = 0
        for i in range(len(self.grid)):
            for j in range(len(self.grid[0])):
                if self.visited[i][j]==0 and self.grid[i][j]==0:
                    isclosed = dfs(i, j)
                    if isclosed==True:
                        ans+=1
        return ans


class Solution:
    
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    
    def __init__(self):
        self.count = 0
    
    @staticmethod
    def _on_board(board, row, col):
        return row >= 0 and row < len(board) and col >= 0 and col < len(board[0])
    
    def _dfs(self, board, row, col, visited) -> bool:
        if (row, col) in visited:
            return True
        
        if not Solution._on_board(board, row, col):
            return False
        
        if board[row][col] == 1:
            return True
        
        visited.add((row, col))
        res = True
        for d in Solution.directions:
            new_row = row + d[0]
            new_col = col + d[1]
            
            if not self._dfs(board, new_row, new_col, visited):
                res = False
        
        return res
            
    
    def closedIsland(self, grid: List[List[int]]) -> int:
        '''
        DFS
        '''
        if not grid or not grid[0]:
            return 0
        
        cnt = 0
        visited = set()
        for m in range(len(grid)):
            for n in range(len(grid[0])):
                if grid[m][n] == 0 and\\
                    (m, n) not in visited and\\
                    self._dfs(grid, m, n, visited):
                    cnt += 1
                    
        return cnt

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: return 0
        self.rows, self.cols = len(grid), len(grid[0])
        self.memo = {}
        ans = 0
        for row in range(self.rows):
            for col in range(self.cols):
                if grid[row][col] == 0:
                    ans += self.dfs(grid, row, col)

        return ans
    def dfs(self, grid, row, col):
        if row < 0 or row > self.rows-1 or col < 0 or col > self.cols - 1:
            return False
        if (row, col) in self.memo:
            return self.memo[(row, col)]
    
        if grid[row][col] == 1:
            return True
        elif row == 0 or row == self.rows - 1 or col == 0 or col == self.cols - 1:
            return False
    
        flag = True
        directions = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]
        grid[row][col] = 1
        for i in range(4):
            r, c = directions[i]
            flag = flag and self.dfs(grid, r, c)

        self.memo[(row, col)] = flag
        return self.memo[(row, col)]



class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        
        row, col = len(grid), len(grid[0])
        output = 0
        
        def dfs(i, j):
            if i in range(row) and j in range(col):
                if grid[i][j] == 0:
                    grid[i][j] = 1

                    # DFS to neighbors
                    bot = dfs(i+1, j)
                    top = dfs(i-1, j)
                    right = dfs(i, j+1)
                    left = dfs(i, j-1)
                    return (bot and top and right and left)
                else:
                    return True
            else:
                return False
                    
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 0:
                    if dfs(i, j):
                        output += 1
                        
        return output

import collections
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        # closed island point rules: (1) it must be 0 (2) it cannot be boundary 
        #   (3) its nb either 1 or 0 (need to append) (4) all connected component follow this rule
        visited = set()
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if (i, j) in visited:
                    continue
                if grid[i][j] == 1:
                    continue
                tmp = self.bfs(grid, i, j, visited)
                # if tmp == 1:
                    #print('found at %d, %d: %s' %(i, j, visited))
                res += tmp
        return res
    def bfs(self, grid, x, y, visited):
        # return 1 if this (BFS connected) is closed island, else 0
        visited.add((x, y))
        # now not boundary, do bfs 
        res = 1 
        q = collections.deque([(x, y)])
        while q:
            x, y = q.pop()
            if self.is_boundary(grid, x, y):
                res = 0 # not closed by water 
            for newx, newy in self.get_nb(grid, x, y):
                if (newx, newy) in visited:
                    continue                
                if grid[newx][newy] == 1:
                    continue # closed by water, stop this direction
                if grid[newx][newy] == 0:
                    q.appendleft((newx, newy))
                    visited.add((newx, newy))
        return res 
    def get_nb(self, grid, x, y):
        COOR = [(0, 1), (0, -1), (-1, 0), (1, 0)]
        res = []
        for deltax, deltay in COOR:
            newx, newy = deltax + x, deltay + y
            if 0 <= newx < len(grid) and 0 <= newy < len(grid[0]):
                res.append((newx, newy))
        return res
    def is_boundary(self, grid, x, y):
        if x == 0 or x == len(grid) - 1:
            return True
        if y == 0 or y == len(grid[0]) - 1:
            return True
        return False

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        closed_island = 0
        if not grid:
            return closed_island
        
        for r in range(1, len(grid)):
            for c in range(1, len(grid[0])):
                if grid[r][c] == 0 and self.dfs(grid, r, c):
                    closed_island += 1
                    
        return closed_island   
    
    def dfs(self,grid, i, j):
            
            if grid[i][j] == 1:
                return True
            
            if i <= 0 or j <= 0 or i >= len(grid) - 1 or j >= len(grid[0]) -1:
                return False
            
            grid[i][j] = 1
            
            top = self.dfs(grid, i - 1, j)
            bottom  = self.dfs(grid, i + 1, j)
            left = self.dfs(grid, i, j - 1)
            right = self.dfs(grid, i, j + 1)
            
            return top and left and right and bottom

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        # find connected 0s not touching any border
        if not grid or not grid[0]:
            return 0
        m = len(grid)
        n = len(grid[0])
        ans = 0
        
        def dfs(i,j,val):
            if 0<=i<m and 0<=j<n and grid[i][j]==0:
                grid[i][j] = val
                dfs(i, j+1, val)
                dfs(i+1, j, val)
                dfs(i-1, j, val)
                dfs(i, j-1, val)

        for i in range(m):
            for j in range(n):
                if (i == 0 or j == 0 or i == m-1 or j == n-1) and grid[i][j] == 0:
                    dfs(i, j, 1)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    dfs(i, j, 1)
                    ans+=1
                    
        return ans
                
        


class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        if len(grid[0]) == 0:
            return 0

        num_islands = 0

        for i in range(0, len(grid)):
            for j in range(0, len(grid[i])):
                if (i == 0 or j == 0 or i == len(grid) - 1 or j == len(grid[0]) - 1):
                    self.closed_island_helper(grid, [i, j])
                    
        for i in range(0, len(grid)):
            for j in range(0, len(grid[i])):
                if grid[i][j] == 1:
                    continue

                num_islands += 1
                self.closed_island_helper(grid, [i, j])
        
        return num_islands
    
    def closed_island_helper(self, grid, coord):
        x, y = coord
        
        if x < 0 or y < 0 or x > len(grid) - 1 or y > len(grid[0]) - 1:
            return

        if x == 0 or y == 0 or x == len(grid) - 1 or y == len(grid[0]) - 1:
            if grid[x][y] == 1:
                return

        if grid[x][y] == 1:
            return

        grid[x][y] = 1

        self.closed_island_helper(grid, [x - 1, y])
        self.closed_island_helper(grid, [x + 1, y])
        self.closed_island_helper(grid, [x, y - 1])
        self.closed_island_helper(grid, [x, y + 1])

        return

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        
        def dfs(i,j,grid):
            if grid[i][j]==1:
                return True
            if i<=0 or j<=0 or i>=n-1 or j>=m-1:
                return False
            grid[i][j]=1
            
            up=dfs(i+1,j,grid)
            down=dfs(i-1,j,grid)
            right=dfs(i,j+1,grid)
            left=dfs(i,j-1,grid)
            
            return up and down and right and left
        
        cnt=0
        n=len(grid)
        m=len(grid[0])
        for i in range(1,n-1):
            for j in range(1,m-1):
                if grid[i][j]==0 and dfs(i,j,grid):
                    cnt+=1
        return cnt


from functools import lru_cache
class Solution:
    def closedIsland(self, grid):
        n=len(grid)
        m=len(grid[0])
        @lru_cache(None)
        def dfs(x,y):
            if x==0 or y==0 or x==n-1 or y==m-1 or grid[x][y]!=0:
                return grid[x][y]!=0
            t=True
            grid[x][y]=-1
            t=dfs(x-1,y) & dfs(x+1,y) & dfs(x,y+1) & dfs(x,y-1)
            return t
        res=0
        for i in range(n):
            for j in range(m):
                if grid[i][j]==0:
                    res+=dfs(i,j)
        return res

from functools import lru_cache
class Solution:
    def closedIsland(self, grid):
        n=len(grid)
        m=len(grid[0])
        @lru_cache(None)
        def dfs(x,y):
            if x==0 or y==0 or x==n-1 or y==m-1 or grid[x][y]!=0:
                return grid[x][y]!=0
            # t=True
            grid[x][y] = -1
            t = dfs(x-1,y) & dfs(x+1,y) & dfs(x,y+1) & dfs(x,y-1)
            return t
        res=0
        for i in range(n):
            for j in range(m):
                if grid[i][j]==0:
                    res+=dfs(i,j)
        return res

class UnionFind:
    
    def __init__(self):
        self.parents = {}
        
    def find(self, a):
        if a in self.parents:
            while a != self.parents[a]:
                a = self.parents[a]
        else:
            self.parents[a] = a
        return self.parents[a]

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a > b: a, b = b, a # always use smaller key
        self.parents[b] = a

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        # union find
        m, n = len(grid), len(grid[0])
        uf = UnionFind()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    if i == 0 or i == m-1 or j == 0 or j == n-1:
                        uf.union((-1,-1), (i,j)) # use (-1,-1) to be edge
                    if i > 0 and grid[i-1][j] == 0:
                        uf.union((i-1,j), (i,j))
                    if j > 0 and grid[i][j-1] == 0:
                        uf.union((i,j-1), (i,j))
                        
        islands = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    tup = uf.find((i,j))
                    if tup != (-1,-1):
                        islands.add(tup)
                    
        # print(islands)
        return len(islands)

from typing import List
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        num_islands = 0
        for row_index, row in enumerate(grid):
            for col_index, val in enumerate(row):
                if val == 0 and self.check_island(grid, row_index, col_index):
                    num_islands += 1
        
        return num_islands
    
    def check_island(self, grid: List[List[int]], row: int, col: int) -> bool:
        if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
            return False
        
        if grid[row][col] == 1:
            return True
        
        grid[row][col] = 1
        top = self.check_island(grid, row - 1, col) 
        bottom = self.check_island(grid, row + 1, col) 
        right =  self.check_island(grid, row, col + 1) 
        left = self.check_island(grid, row, col - 1) 
        
        return top and bottom and right and left

class Solution(object):
    def closedIsland(self, grid):
        \"\"\"
        :type grid: List[List[int]]
        :rtype: int
        \"\"\"
        if not grid or not grid[0]:
            return 0
        
        m, n = len(grid), len(grid[0])
        
        def dfs(i, j, val):
            if 0<=i<m and 0<=j<n and grid[i][j]==0:
                grid[i][j] = val
                dfs(i, j+1, val)
                dfs(i+1, j, val)
                dfs(i-1, j, val)
                dfs(i, j-1, val)
        
        for i in range(m):
            for j in range(n):
                if (i == 0 or j == 0 or i == m-1 or j == n-1) and grid[i][j] == 0:
                    dfs(i, j, 1)
                
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    dfs(i, j, 1)
                    res += 1
                    
        return res
                    
                    
        
    

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        if not grid: return 0
        
        m,n = len(grid),len(grid[0])
        
        numIslands = 0
        for i in range(m):
            for j in range(n):
                if (i == 0 or j == 0 or i == m-1 or j == n-1) and grid[i][j] == 0:
                    self.dfs(grid, i, j, 1)
        
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    self.dfs(grid, i, j, 1)
                    numIslands += 1
                    
        return numIslands
    
    def dfs(self,grid,i,j,val):
        m,n = len(grid),len(grid[0])
        
        grid[i][j] = val
        for newi,newj in ((i+1,j),(i-1,j),(i,j-1),(i,j+1)):
            if 0 <= newi < m and 0 <= newj < n and grid[newi][newj] == 0:
                   # grid[newi][newj] = val
                    self.dfs(grid,newi,newj,val)


class Solution(object):
    def closedIsland(self, grid):
        \"\"\"
        :type grid: List[List[int]]
        :rtype: int
        \"\"\"
        if not grid or not grid[0]:
            return 0
        
        m, n = len(grid), len(grid[0])
        
        def dfs(i, j, val):
            if 0<=i<m and 0<=j<n and grid[i][j]==0:
                grid[i][j] = val
                dfs(i, j+1, val)
                dfs(i+1, j, val)
                dfs(i-1, j, val)
                dfs(i, j-1, val)
        
        for i in range(m):
            for j in range(n):
                if (i == 0 or j == 0 or i == m-1 or j == n-1) and grid[i][j] == 0:
                    dfs(i, j, 1)
                
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    dfs(i, j, 1)
                    res += 1
                    
        return res

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        # we perform bfs to find connected components and from all the connected components we remove those that have a node on the edges
        # first we create a set of nodes that can act as start nodes
        possible_start = set()
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 0:
                    possible_start.add((i,j))
        # now we need to perform bfs from each possible start and find the connected components
        answer = 0
        directions = [(-1,0),(1,0),(0,-1),(0,1)]
        while possible_start != set():
            start = possible_start.pop()
            # print('start',start)
            queue = [start]
            visited = set([start])
            if 0 == start[0] or start[0] == len(grid)-1 or 0 == start[1] or start[1] ==  len(grid[1])-1 :
                remove_this_island = True
            else:
                remove_this_island = False
            while queue != []:
                c = queue.pop(0)
                # print(c)
                for d in directions:
                    n = (c[0] + d[0] , c[1] + d[1]) 
                    if 0 <= n[0] < len(grid) and 0 <= n[1] < len(grid[0]):
                        if grid[n[0]][n[1]] == 0:
                            if 0 == n[0] or n[0] == len(grid)-1 or 0 == n[1] or n[1] ==  len(grid[1])-1 :
                                remove_this_island = True
                            if n not in visited:
                                queue.append(n)
                                visited.add(n)
                        
            # print(visited,remove_this_island)
            # at the end of the bfs we check if we need to consider this island or not
            possible_start = possible_start - visited
            if not remove_this_island:
                answer += 1
            
        return answer

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        if rows == 0:
            return 0 
        
        cols = len(grid[0])
        if cols == 0:
            return 0
        
        count = 0
        
        def recur(x, y):
            if not 0 <= x < rows or not 0 <= y < cols:
                return False
            
            if grid[x][y] == 1:
                return True
            
            grid[x][y] = 1
            
            right = recur(x + 1, y)
            left = recur(x - 1, y)
            top = recur(x, y + 1) 
            bot = recur(x, y - 1)
            return right and left and top and bot
        
        
        for x in range(rows):
            for y in range(cols):
                if grid[x][y] == 0 and recur(x, y):
                    count += 1
        return count
    
    


from collections import defaultdict
dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]

class DSU:
    def __init__(self, n):
        self.n = n
        self.parent = [x for x in range(n)]
        self.rank = [0 for x in range(n)]
        self.land = [False for x in range(n)]
        
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, s, t):
        sp, tp = self.find(s), self.find(t)
        if sp == tp:
            return
        if self.rank[sp] > self.rank[tp]:
            self.parent[tp] = sp
        elif self.rank[sp] < self.rank[tp]:
            self.parent[sp] = tp
        else:
            self.parent[sp] = tp
            self.rank[tp] += 1
        
        
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        # 0 is land,  1 is water!
        m, n = len(grid), len(grid[0])
        net = DSU(m * n)
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    continue
                # grid[r][c] = 0: land
                net.land[r * n + c] = True
                for d in dirs:
                    nr, nc = r + d[0], c + d[1]
                    if not (0 <= nr < m) or not (0 <= nc < n):
                        continue
                    elif grid[nr][nc] == 1:
                        continue
                    net.union(r * n + c, nr * n + nc)
        ihm = defaultdict(list) # island hashmap
        for i in range(m * n):
            p = net.find(i) # parent
            if net.land[p]:
                ihm[p].append((i // n, i % n))
        islands = list(ihm.values()) # list of list of integer
        ret = 0
        for pl in islands: # point list
            isClosed = True
            for p in pl: # point
                r, c = p[0], p[1]
                if r == m - 1 or c == n - 1 or r == 0 or c == 0:
                    isClosed = False
                    break
            if isClosed:
                ret += 1
        return ret
                    


class Solution:\r
    LAND = 0\r
    WATER = 1\r
    def closedIsland(self, grid: List[List[int]]) -> int:\r
        if not grid:\r
            return 0\r
        count=0\r
        m, n, count = len(grid), len(grid[0]) if grid else 0, 0           \r
        for i in range(1, len(grid)-1):\r
            for j in range(1, len(grid[0])-1):\r
                if grid[i][j]==self.LAND and self.dfs(i,j,grid) :\r
                 count +=1\r
        return count\r
    def inside_grid(self,x, y,grid):\r
        return 0 <= x < len(grid) and 0 <= y < len(grid[0])\r
    \r
    def dfs(self,i,j,grid):\r
        #m, n = len(grid), len(grid[0]) if grid else 0       \r
        #Test = True\r
        if grid[i][j]==self.WATER:\r
            Test = True\r
            return True\r
        \r
        if(i<=0 or j<=0 or j>= len(grid[0])-1 or i >= len(grid)-1):\r
            Test = False\r
            return False\r
        grid[i][j] = self.WATER \r
        Test= True & self.dfs(i+1,j,grid)\r
        Test= Test& self.dfs(i-1,j,grid)\r
        Test= Test& self.dfs(i,j+1,grid)\r
        Test= Test& self.dfs(i,j-1,grid)\r
        return Test  \r
# c= Solution()\r
# grid=[[1,1,0,1,1,1,1,1,1,1],[0,0,1,0,0,1,0,1,1,1],[1,0,1,0,0,0,1,0,1,0],[1,1,1,1,1,0,0,1,0,0],[1,0,1,0,1,1,1,1,1,0],[0,0,0,0,1,1,0,0,0,0],[1,0,1,0,0,0,0,1,1,0],[1,1,0,0,1,1,0,0,0,0],[0,0,0,1,1,0,1,1,1,0],[1,1,0,1,0,1,0,0,1,0]]\r
# grid2=[[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]\r
# c.closedIsland(grid)

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0

        islands = 0

        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if row == 0 or row == len(grid)-1 or col == 0 or col == len(grid[0])-1:
                    if grid[row][col] == 0:
                        self.dfs(grid, row, col)

        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 0:
                    islands += 1
                    self.dfs(grid, row, col)

        return islands


    def dfs(self, grid, row, col):
        grid[row][col] = 1

        for i, j in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            if 0 <= row + i < len(grid) and 0 <= col + j < len(grid[0]):
                if grid[row+i][col+j] == 0:
                    self.dfs(grid, row+i, col+j)


class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        touched = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
        num_islands = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if touched[i][j] or grid[i][j]:
                    continue
                    
                island = True
                to_explore = [[i, j]]
                while to_explore:
                    c_i, c_j = to_explore.pop(0)
                    
                    if c_i - 1 < 0:
                        island = False
                    elif not touched[c_i - 1][c_j] and not grid[c_i - 1][c_j]:
                        to_explore.append([c_i - 1, c_j])
                    
                    if c_i + 1 >= len(grid):
                        island = False
                    elif not touched[c_i + 1][c_j] and not grid[c_i + 1][c_j]:
                        to_explore.append([c_i + 1, c_j])
                        
                    if c_j - 1 < 0:
                        island = False
                    elif not touched[c_i][c_j - 1] and not grid[c_i][c_j - 1]:
                        to_explore.append([c_i, c_j - 1])
                    
                    if c_j + 1 >= len(grid[0]):
                        island = False
                    elif not touched[c_i][c_j + 1] and not grid[c_i][c_j + 1]:
                        to_explore.append([c_i, c_j + 1])
                        
                    touched[c_i][c_j] = 1
                
                if island:
                    num_islands += 1
        return num_islands

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        M,N = len(grid),len(grid[0])
        moves = ((1,0),(-1,0),(0,1),(0,-1))
        def dfs(x,y):
            grid[x][y] = 1
            for dx,dy in moves:
                if 0<=x+dx<M and 0<=y+dy<N and grid[x+dx][y+dy]==0:
                    dfs(x+dx,y+dy)
        
        #eliminate outer islands
        for i in range(M):
            if grid[i][0] == 0:     dfs(i,0)
            if grid[i][N-1] == 0:   dfs(i,N-1)
        for j in range(N):
            if grid[0][j] == 0:     dfs(0,j)
            if grid[M-1][j] == 0:   dfs(M-1,j)
        #count ans
        ans = 0
        for i in range(1,M-1):
            for j in range(1,N-1):
                if grid[i][j] == 0:
                    ans += 1
                    dfs(i,j)
        return ans

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        self.m = len(grid)
        self.n = len(grid[0])
        
        #for row in grid:
        #    print(row)
        
        def dfs(i, j):
            if i == 0 or j == 0 or i == self.m - 1 or j == self.n - 1:
                return False
            else:
                for vi, vj in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                    newI = vi + i
                    newJ = vj + j
                    if grid[newI][newJ] == 0:
                        #if self.total == 4:
                        #    print(newI, newJ)
                        grid[newI][newJ] = 1
                        self.curPath.append((newI, newJ))
                        
                        #print('what')
                        if not dfs(newI, newJ):
                            return False
            
            #for k, h in self.curPath:
            #    grid[k][h] = self.total+2
            return True
                    
                            
        self.total = 0
        for i in range(1, self.m - 1):
            for j in range(1, self.n - 1):
                if grid[i][j] == 0:
                    #print(i, j)
                    grid[i][j] = 1
                    self.curPath = [(i, j)]
                    if dfs(i, j):
                        self.total += 1
                        #print(self.curPath, len(self.curPath), -self.total)
                        for k, h in self.curPath:
                            grid[k][h] = -self.total
                    else:
                        for k, h in self.curPath:
                            grid[k][h] = 0
                            
                        #for row in grid:
                        #    print(row)
        return self.total

import queue

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        
        output = 0
        m = len(grid)
        n = len(grid[0])
        for ii in range(m):
            for jj in range(n):
                if grid[ii][jj] == 0:
                    q = queue.Queue()
                    q.put((ii,jj))
                    grid[ii][jj] = 2
                    flag = True
                    while not q.empty():
                        x,y = q.get()
                        if x == 0 or x == m-1 or y == 0 or y == n-1:
                            flag = False 
                        for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
                            if 0<=x+dx<m and 0<=y+dy<n and grid[x+dx][y+dy] == 0:
                                q.put((x+dx,y+dy))
                                grid[x+dx][y+dy] = 2
                    if flag:
                        output += 1
        return output

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        visited = [[False] * len(grid[0]) for i in range(len(grid))]
        # bfs island 0s and return True if the island has no point on grid boarder
        def dfs(grid: List[List[int]], visited: List[List[int]], x, y) -> bool:
            closedIsland = not (x == 0 or y == 0 or x == len(grid) - 1 or y == len(grid[0]) - 1)
            queue = [(x,y)]
            while queue:
                x,y = queue.pop()
                for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
                    nx,ny = x+dx,y+dy
                    if 0<=nx<len(grid) and 0<=ny<len(grid[0]) and not visited[nx][ny] and grid[nx][ny] == 0:
                        visited[nx][ny] = True
                        queue.append((nx,ny))
                        if nx == 0 or ny == 0 or nx == len(grid) - 1 or ny == len(grid[0]) - 1:
                            closedIsland = False
            
            return closedIsland
        
        ans = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if not visited[i][j] and grid[i][j] == 0:
                    ans += 1 if dfs(grid, visited, i, j) else 0
        
        return ans

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        if(len(grid) == 0):
            return 0
        m = len(grid)
        n = len(grid[0])
        for col in range(n):
            if(grid[0][col] == 0):
                self.dfs(0,col,grid)
            if(grid[m-1][col] == 0):
                self.dfs(m-1,col,grid)
        for row in range(m):
            if(grid[row][0] == 0):
                self.dfs(row, 0, grid)
            if(grid[row][n-1] == 0):
                self.dfs(row,n-1, grid)
        components = 0
        for i in range(m):
            for j in range(n):
                if(grid[i][j] == 0):
                    self.dfs(i,j,grid)
                    components += 1
        return components
    
    def dfs(self, i, j, grid):
        grid[i][j] = 1
        stack = [(i,j)]
        directions = [(0,1),(1,0),(0,-1),(-1,0)]
        while(stack):
            x,y = stack.pop()
            for dx,dy in directions:
                if(x+dx<0 or y+dy<0 or x+dx >=len(grid) or y+dy>=len(grid[0])):
                    continue
                if(grid[x+dx][y+dy] == 0):
                    grid[x+dx][y+dy] = 1
                    stack.append((x+dx,y+dy))

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        row = len(grid)
        column = len(grid[0])
        ans = 0
        
        def bfs(x, y):
            queue = [(x, y)]
            near_border = False
            while queue:
                r, c = queue.pop(0)
                grid[r][c] = 1
                if r == 0 or c == 0 or r == row - 1 or c == column - 1:
                    near_border = True
                for r_, c_ in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    newr, newc = r + r_, c + c_
                    if 0 <= newr < row and 0 <= newc < column and grid[newr][newc] == 0:
                        queue.append((newr, newc))
            if not near_border:
                nonlocal ans
                ans += 1
        for r in range(row):
            for c in range(column):
                if grid[r][c] == 0:
                    bfs(r, c)
        return ans

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        row = len(grid)
        column = len(grid[0])
        ans = 0
        
        def bfs(x, y):
            queue = [(x, y)]
            near_border = False
            while queue:
                r, c = queue.pop(0)
                grid[r][c] = 1
                if r == 0 or c == 0 or r == row - 1 or c == column - 1:
                    near_border = True
                for r_, c_ in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    newr, newc = r + r_, c + c_
                    if 0 <= newr < row and 0 <= newc < column and grid[newr][newc] == 0:
                        queue.append((newr, newc))
            if not near_border:
                nonlocal ans
                ans += 1
        for r in range(row):
            for c in range(column):
                if grid[r][c] == 0:
                    bfs(r, c)
        return ans   

'''
Recursion
https://www.youtube.com/watch?v=MnD8KhBHgRo
'''
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        if not grid or len(grid) == 0:
            return 0 
        
        closedIslands = 0
        R, C = len(grid), len(grid[0])
        
        for i in range(1, R-1):
            for j in range(1, C-1):
                if grid[i][j] == 0:
                    if self.isClosedIslands(grid, i, j, R, C):
                        closedIslands += 1
        
        return closedIslands
    
    def isClosedIslands(self, grid, i, j, R, C):
        # -1 = visited
        # 1 = water
        # 0 = land
        # If we encounter -1 or 1, it's still considered an island thus far. We consider those elements as part of our island or surrounding our island.
        if grid[i][j] == -1 or grid[i][j] == 1:
            return True
        
        # We know we have a 0(land). If the element is on the perimeter, it can't be a closed island. 
        if self.isOnPerimeter(i, j, R, C):
            return False        
        grid[i][j] = -1
        
        # Check directions
        left = self.isClosedIslands(grid, i, j-1, R, C)
        right = self.isClosedIslands(grid, i, j+1, R, C)
        up = self.isClosedIslands(grid, i-1, j, R, C)
        down = self.isClosedIslands(grid, i+1, j, R, C)
        
        return left and right and up and down
    
    def isOnPerimeter(self, i, j, R, C):
        return i == 0 or j == 0 or i == R-1 or j == C-1
        



from typing import List, Tuple, Set


class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        height = len(grid)
        assert height > 0, f\"Grid must have at least one row but has {len(grid)} rows\"
        width = len(grid[0])
        seen_land: Set[Tuple[int, int]] = set()

        def mark_all_connected_and_check_is_island(point_x: int, point_y: int) -> int:
            seen_land.add((point_x, point_y))
            is_island = (
                point_x != 0
                and point_y != 0
                and point_x < width - 1
                and point_y < height - 1
            )
            for (x, y) in [
                (point_x - 1, point_y),
                (point_x + 1, point_y),
                (point_x, point_y - 1),
                (point_x, point_y + 1),
            ]:
                try:
                    if grid[y][x] != 0:
                        continue
                except IndexError:
                    continue
                if (x, y) in seen_land:
                    continue
                is_island &= mark_all_connected_and_check_is_island(x, y)
            return is_island

        num_islands = 0
        for y, row in enumerate(grid):
            for x, cell in enumerate(row):
                if cell == 1:
                    continue
                elif cell == 0:
                    if (x, y) not in seen_land:
                        is_island = mark_all_connected_and_check_is_island(x, y)
                        if is_island:
                            num_islands += 1
                else:
                    assert False, f\"Cell ({x},{y}) is {cell} but expected 0 or 1\"
        return num_islands


def test_example_1() -> None:
    assert (
        Solution().closedIsland(
            [
                [1, 1, 1, 1, 1, 1, 1, 0],
                [1, 0, 0, 0, 0, 1, 1, 0],
                [1, 0, 1, 0, 1, 1, 1, 0],
                [1, 0, 0, 0, 0, 1, 0, 1],
                [1, 1, 1, 1, 1, 1, 1, 0],
            ]
        )
        == 2
    )


def test_example_2() -> None:
    assert (
        Solution().closedIsland([[0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 1, 1, 1, 0]])
        == 1
    )


def test_example_3() -> None:
    assert (
        Solution().closedIsland(
            [
                [1, 1, 1, 1, 1, 1, 1],
                [1, 0, 0, 0, 0, 0, 1],
                [1, 0, 1, 1, 1, 0, 1],
                [1, 0, 1, 0, 1, 0, 1],
                [1, 0, 1, 1, 1, 0, 1],
                [1, 0, 0, 0, 0, 0, 1],
                [1, 1, 1, 1, 1, 1, 1],
            ]
        )
        == 2
    )


def test_simplest_grids() -> None:
    assert Solution().closedIsland([[0]]) == 0
    assert Solution().closedIsland([[1]]) == 0


def test_simplest_island() -> None:
    assert Solution().closedIsland([[1, 1, 1], [1, 0, 1], [1, 1, 1]]) == 1


from enum import IntEnum
from typing import List, Tuple, Set


class Tile(IntEnum):
    LAND = 0
    WATER = 1


class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        height = len(grid)
        assert height > 0, f\"Grid must have at least one row but has {height} rows\"
        width = len(grid[0])

        def delete_connected_land(x: int, y: int) -> None:
            if grid[y][x] == Tile.WATER:
                return
            grid[y][x] = Tile.WATER
            if x > 0:
                delete_connected_land(x - 1, y)
            if y > 0:
                delete_connected_land(x, y - 1)
            if x < width - 1:
                delete_connected_land(x + 1, y)
            if y < height - 1:
                delete_connected_land(x, y + 1)

        for y in [0, height - 1]:
            for x in range(width):
                delete_connected_land(x, y)

        for y in range(height):
            for x in [0, width - 1]:
                delete_connected_land(x, y)

        num_islands = 0
        for y, row in enumerate(grid):
            for x, cell in enumerate(row):
                if grid[y][x] == Tile.LAND:
                    num_islands += 1
                    delete_connected_land(x, y)
        return num_islands

from collections import deque
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        ans = 0
        seen = set()
        m, n = len(grid), len(grid[0])
        moves = [(0, 1), (1, 0), (-1, 0), (0, -1)]
        for i in range (m):
            for j in range (n):
                if (i, j) not in seen and grid[i][j] == 0:
                    curr_seen = {(i, j)}
                    q = deque([(i, j)])
                    closed = True
                    while q:
                        x, y = q.popleft()
                        curr_seen.add((x, y))
                        if x == 0 or x == m - 1 or y == 0 or y == n - 1:
                            closed = False
                            
                        for dx, dy in moves:
                            next_x, next_y = x + dx, y + dy
                            if 0 <= next_x < m and 0 <= next_y < n:
                                if grid[next_x][next_y] == 0:
                                    if (next_x, next_y) not in curr_seen:
                                        curr_seen.add((next_x, next_y))
                                        q.append((next_x, next_y))         
                    if closed:
                        ans += 1
                    seen = seen | curr_seen
        return ans

from enum import IntEnum
from typing import List, Tuple, Set


class Tile(IntEnum):
    LAND = 0
    WATER = 1


class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        height = len(grid)
        assert height > 0, f\"Grid must have at least one row but has {height} rows\"
        width = len(grid[0])
        seen_land: List[List[bool]] = [
            [False for _ in range(width)] for _ in range(height)
        ]

        num_islands = 0
        for y, row in enumerate(grid):
            for x, tile in enumerate(row):
                if tile != Tile.LAND or seen_land[y][x]:
                    continue
                else:
                    to_check = {(x, y)}
                    is_island = True
                    while to_check:
                        x1, y1 = to_check.pop()
                        seen_land[y1][x1] = True
                        is_island &= 0 < x1 < width - 1 and 0 < y1 < height - 1
                        for (x2, y2) in [
                            (x1 - 1, y1),
                            (x1 + 1, y1),
                            (x1, y1 - 1),
                            (x1, y1 + 1),
                        ]:
                            if (
                                0 <= x2 < width
                                and 0 <= y2 < height
                                and not seen_land[y2][x2]
                                and grid[y2][x2] == Tile.LAND
                            ):
                                to_check.add((x2, y2))
                    if is_island:
                        num_islands += 1
        return num_islands

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        height = len(grid)
        width = len(grid[0])
        for i in range(height):
            if grid[i][0] == 0:
                grid[i][0] = -2
            if grid[i][width-1] == 0:
                grid[i][width-1] = -2
        
        for j in range(width):
            if grid[0][j] == 0:
                grid[0][j] = -2
            if grid[height-1][j] == 0:
                grid[height-1][j] = -2

        count = 0
        for i in range(1, height-1):
            for j in range(1, width-1):
                flag = 0
                visted_list = []
                if grid[i][j] == 0:
                    visted_list.append([i,j])
                    grid[i][j]=-1
                    
                    while len(visted_list) > 0:
                        current_index = visted_list.pop()
                        ii = current_index[0]
                        jj = current_index[1]

                        indexes = [(ii-1, jj), (ii+1, jj), (ii, jj-1), (ii,jj+1)]
                        for a, b in indexes:
                            if grid[a][b] == 0:
                                visted_list.append([a,b])
                                grid[a][b]=-1
                            if grid[a][b] == -2:
                                flag = 1
                    if flag == 0:
                        count += 1
                    
        return count

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        seen =  set([])
        stack =  []
        closed = True
        count = 0
        
        rows = len(grid)
        cols =  len(grid[0])
        
        for row in range(rows): 
            for col in range(cols): 
                if not grid[row][col] and (row,col) not in seen:
                    closed = True
                    stack.append((row,col))
                    while len(stack) > 0: 
                        node = stack.pop() 
                        if node in seen: continue
                        if node[0]-1>=0 and not grid[node[0]-1][node[1]] and (node[0]-1,node[1]) not in seen:  
                            stack.append((node[0]-1,node[1]))
                        elif node[0]-1 < 0: 
                            closed = False
                        if node[1]-1>=0 and not grid[node[0]][node[1]-1] and (node[0],node[1]-1) not in seen:
                            stack.append((node[0],node[1]-1))
                        elif node[1]-1 < 0:
                            closed = False
                        if node[0]+1 < rows and not grid[node[0]+1][node[1]] and (node[0]+1,node[1]) not in seen:  
                            stack.append((node[0]+1,node[1]))
                        elif node[0]+1 >= rows:
                            closed = False
                        if node[1]+1 < cols and not grid[node[0]][node[1]+1] and (node[0],node[1]+1) not in seen:
                            stack.append((node[0],node[1]+1))
                        elif node[1]+1 >= cols:
                            closed = False
                        seen.add(node)
                    if closed: count += 1
 
        return count

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        # time O(mn); space O(1)
        def DFS(row, col):
            if row < 0 or row >= nrow or col < 0 or col >= ncol:
                return True
            elif grid[row][col] == 1:
                return False
            else:
                grid[row][col] = 1
                connect_boundary = False
                for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    new_row, new_col = row + dx, col + dy
                    if DFS(new_row, new_col):
                        connect_boundary = True
                return connect_boundary
        
        nrow, ncol = len(grid), len(grid[0])
        cnt = 0
        for row in range(nrow):
            for col in range(ncol):
                if grid[row][col] == 0:
                    if not DFS(row, col):
                        cnt += 1
        
        return cnt

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]: return 0
        self.rows, self.cols = len(grid), len(grid[0])
        ans = 0
        for i in range(self.rows):
            for j in range(self.cols):
                if grid[i][j] == 0 and self.dfs(grid, i, j):
                    ans += 1

        return ans
    def dfs(self, grid, row, col):
        if row < 0 or row > self.rows-1 or col < 0 or col > self.cols - 1:
            return False
    
        if grid[row][col] == 1 or grid[row][col] == 2:
            return True

        grid[row][col] = 2
        up = self.dfs(grid, row - 1, col)
        down = self.dfs(grid, row + 1, col)
        left = self.dfs(grid,  row, col - 1)
        right = self.dfs(grid,  row, col + 1)
        if up and down and left and right:
            return True
        else:
            return False


from collections import deque

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        self.m, self.n = m, n
        visited = [[False]*n for _ in range(m)]
        Q = deque()
        count = 0
        for i in range(m):
            for j in range(n):
                if visited[i][j] or (grid[i][j] == 1):
                    continue
                visited[i][j] = True
                Q.append((i,j))
                edge_found = False
                while len(Q) > 0:
                    x,y = Q.popleft()
                    #print(x,y)
                    if self.is_edge(x, y):
                        edge_found = True
                    for p,q in self.nbrs(x, y):
                        if (not visited[p][q]) and (grid[p][q] == 0):
                            #print('adding ', p, q)
                            visited[p][q] = True
                            Q.append((p,q))
                if not edge_found:
                    count += 1
        return count
                            
    def is_edge(self, i, j):
        return (i == 0) or (i == self.m - 1) or (j == 0) or (j == self.n - 1)
                    
    def nbrs(self, i, j):
        for d in (-1, 1):
            if (0 <= i + d < self.m):
                yield (i + d, j)
            if (0 <= j + d < self.n):
                yield (i, j + d)