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

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Data structures

Graph traversal

Spanning trees

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):
		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.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:

	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
					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:
		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)
				res += tmp
		return res

	def bfs(self, grid, x, y, visited):
		visited.add((x, y))
		res = 1
		q = collections.deque([(x, y)])
		while q:
			(x, y) = q.pop()
			if self.is_boundary(grid, x, y):
				res = 0
			for (newx, newy) in self.get_nb(grid, x, y):
				if (newx, newy) in visited:
					continue
				if grid[newx][newy] == 1:
					continue
				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:
		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


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)
		self.parents[b] = a

class Solution:

	def closedIsland(self, grid: List[List[int]]) -> int:
		(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))
					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)
		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:

	def closedIsland(self, grid: List[List[int]]) -> int:
		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))
		answer = 0
		directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
		while possible_start != set():
			start = possible_start.pop()
			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)
				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)
			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:
		(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
				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)
		for i in range(m * n):
			p = net.find(i)
			if net.land[p]:
				ihm[p].append((i // n, i % n))
		islands = list(ihm.values())
		ret = 0
		for pl in islands:
			isClosed = True
			for p in pl:
				(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:

	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)
		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)
		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])

		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:
						grid[newI][newJ] = 1
						self.curPath.append((newI, newJ))
						if not dfs(newI, newJ):
							return False
			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:
					grid[i][j] = 1
					self.curPath = [(i, j)]
					if dfs(i, j):
						self.total += 1
						for (k, h) in self.curPath:
							grid[k][h] = -self.total
					else:
						for (k, h) in self.curPath:
							grid[k][h] = 0
		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))]

		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:
		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):
		if grid[i][j] == -1 or grid[i][j] == 1:
			return True
		if self.isOnPerimeter(i, j, R, C):
			return False
		grid[i][j] = -1
		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 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


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:

		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()
					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:
							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)