Given a binary matrix mat[][] of dimensions NxM such that 1 denotes land and 0 denotes water. Find the number of closed islands in the given matrix. 
Note: A closed island is a group of 1s surrounded by only 0s on all the boundaries (except diagonals). In simple words, a closed island is an island whose none of the 1s lie on the edges of the matrix.
Example 1:
Input:
N = 5, M = 8
mat[][] = {{0, 0, 0, 0, 0, 0, 0, 1}, 
           {0, 1, 1, 1, 1, 0, 0, 1}, 
           {0, 1, 0, 1, 0, 0, 0, 1}, 
           {0, 1, 1, 1, 1, 0, 1, 0}, 
           {1, 0, 0, 0, 0, 1, 0, 1}}
Output:
2
Explanation:
mat[][] = {{0, 0, 0, 0, 0, 0, 0, 1}, 
           {0, 1, 1, 1, 1, 0, 0, 1}, 
           {0, 1, 0, 1, 0, 0, 0, 1}, 
           {0, 1, 1, 1, 1, 0, 1, 0}, 
           {1, 0, 0, 0, 0, 1, 0, 1}} 
There are 2 closed islands. The islands in dark are closed because they are completely surrounded by 0s (water). There are two more islands in the last column of the matrix, but they are not completely surrounded by 0s. Hence they are not closed islands. 
Example 2:
Input:
N = 3, M = 3
mat[][] = {{1, 0, 0},
           {0, 1, 0},
           {0, 0, 1}}
Output: 
1
Explanation:
mat[][] = {{1, 0, 0},
          {0, 1, 0},
          {0, 0, 1}}
There is just a one closed island.
Your task:
You dont need to read input or print anything. Your task is to complete the function closedIslands() which takes two integers N and M, and a 2D binary matrix mat as input parameters and returns the number of closed islands.
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N*M)
Constraints:
1 ≤ N,M ≤ 500

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Spanning trees

Matrices

Data structures
Skill types: Data structures
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(N*M)

Starter code:
#User function Template for python3



class Solution:

	def closedIslands(self, matrix, N, M):

		#Code here

Solutions:
class Solution:

	def dfs(self, matrix, N, M, i, j):
		matrix[i][j] = 0
		if i in (0, N - 1) or j in (0, M - 1):
			return False
		flag1 = True
		flag2 = True
		flag3 = True
		flag4 = True
		if i >= 1 and matrix[i - 1][j]:
			flag1 = self.dfs(matrix, N, M, i - 1, j)
		if i <= N - 1 and matrix[i + 1][j]:
			flag2 = self.dfs(matrix, N, M, i + 1, j)
		if j >= 1 and matrix[i][j - 1]:
			flag3 = self.dfs(matrix, N, M, i, j - 1)
		if j <= M - 1 and matrix[i][j + 1]:
			flag4 = self.dfs(matrix, N, M, i, j + 1)
		return flag1 and flag2 and flag3 and flag4

	def closedIslands(self, matrix, N, M):
		count = 0
		for i in range(1, N - 1):
			for j in range(1, M - 1):
				if matrix[i][j] == 1 and self.dfs(matrix, N, M, i, j):
					count += 1
		return count


class Solution:

	def closedIslands(self, matrix, N, M):
		count = 0

		def dfs(matrix, N, M, x, y):
			matrix[x][y] = 0
			v1 = v2 = v3 = v4 = True
			if x - 1 >= 0 and y >= 0 and (x - 1 < N) and (y < M):
				if matrix[x - 1][y] == 1:
					v1 = dfs(matrix, N, M, x - 1, y)
			if x >= 0 and y - 1 >= 0 and (x < N) and (y - 1 < M):
				if matrix[x][y - 1] == 1:
					v2 = dfs(matrix, N, M, x, y - 1)
			if x >= 0 and y + 1 >= 0 and (x < N) and (y + 1 < M):
				if matrix[x][y + 1] == 1:
					v3 = dfs(matrix, N, M, x, y + 1)
			if x + 1 >= 0 and y >= 0 and (x + 1 < N) and (y < M):
				if matrix[x + 1][y] == 1:
					v4 = dfs(matrix, N, M, x + 1, y)
			if x == 0 or y == 0 or x == N - 1 or (y == M - 1):
				return False
			return all([v1, v2, v3, v4])
		for i in range(N):
			for j in range(M):
				val = False
				if matrix[i][j] != 0:
					val = dfs(matrix, N, M, i, j)
				if val:
					count += 1
		return count


class Solution:

	def dfs(self, matrix, visited, x, y, n, m, hasCornerCell):
		if x < 0 or y < 0 or x >= n or (y >= m) or (visited[x][y] == True) or (matrix[x][y] == 0):
			return
		if x == 0 or y == 0 or x == n - 1 or (y == m - 1):
			if matrix[x][y] == 1:
				hasCornerCell[0] = True
		visited[x][y] = True
		self.dfs(matrix, visited, x + 1, y, n, m, hasCornerCell)
		self.dfs(matrix, visited, x, y + 1, n, m, hasCornerCell)
		self.dfs(matrix, visited, x - 1, y, n, m, hasCornerCell)
		self.dfs(matrix, visited, x, y - 1, n, m, hasCornerCell)

	def closedIslands(self, matrix, n, m):
		visited = [[False for i in range(m)] for j in range(n)]
		result = 0
		for i in range(n):
			for j in range(m):
				if (i != 0 and j != 0 and (i != n - 1) and (j != m - 1)) and matrix[i][j] == 1 and (visited[i][j] == False):
					hasCornerCell = [False]
					self.dfs(matrix, visited, i, j, n, m, hasCornerCell)
					if not hasCornerCell[0]:
						result = result + 1
		return result


class Solution:

	def closedIslands(self, matrix, N, M):
		v = [[0] * (M + 1) for nn in range(N + 1)]
		n = N
		m = M

		def dfs(i, j, a, v, n, m):
			if (i < 0 or i >= n) or (j < 0 or j >= m) or a[i][j] != 1:
				return
			v[i][j] = 1
			if v[i - 1][j] == 0:
				dfs(i - 1, j, a, v, n, m)
			if v[i][j - 1] == 0:
				dfs(i, j - 1, a, v, n, m)
			if v[i][j + 1] == 0:
				dfs(i, j + 1, a, v, n, m)
			if v[i + 1][j] == 0:
				dfs(i + 1, j, a, v, n, m)
			return
		ans = 0
		for i in range(n):
			for j in range(m):
				if v[i][j] == 0 and matrix[i][j] == 1:
					dfs(i, j, matrix, v, n, m)
					ans += 1
		v = [[0] * (M + 1) for nn in range(N + 1)]
		for i in range(n):
			if v[i][0] == 0 and matrix[i][0] == 1:
				dfs(i, 0, matrix, v, n, m)
				ans -= 1
			if v[i][m - 1] == 0 and matrix[i][m - 1] == 1:
				dfs(i, m - 1, matrix, v, n, m)
				ans -= 1
		for j in range(m):
			if v[0][j] == 0 and matrix[0][j] == 1:
				dfs(0, j, matrix, v, n, m)
				ans -= 1
			if v[n - 1][j] == 0 and matrix[n - 1][j] == 1:
				dfs(n - 1, j, matrix, v, n, m)
				ans -= 1
		return ans


from collections import deque

class Solution:

	def closedIslands(self, a, n, m):
		vis = []
		row = [0, -1, 0, 1]
		col = [-1, 0, 1, 0]
		q = deque()
		for i in a:
			vis.append(i)
		for i in range(n):
			for j in range(m):
				if (i == 0 or j == 0 or n - 1 == i or (j == m - 1)) and vis[i][j] == 1:
					vis[i][j] = 0
					q.append((i, j))

		def bfs():
			while q:
				(r, c) = q.popleft()
				for k in range(4):
					ro = r + row[k]
					co = c + col[k]
					if ro >= 0 and co >= 0 and (ro < n) and (co < m) and (vis[ro][co] == 1):
						q.append((ro, co))
						vis[ro][co] = 0
		bfs()
		cou = 0
		for i in range(n):
			for j in range(m):
				if i != 0 and j != 0 and vis[i][j]:
					cou += 1
					q.append((i, j))
					vis[i][j] = 0
					bfs()
		return cou


class Solution:

	def closedIslands(self, matrix, N, M):
		visited = set()

		def dfs(r, c):
			if r >= N or r < 0 or c >= M or (c < 0):
				return False
			if matrix[r][c] == 0 or (r, c) in visited:
				return True
			visited.add((r, c))
			f1 = dfs(r + 1, c)
			f2 = dfs(r - 1, c)
			f3 = dfs(r, c + 1)
			f4 = dfs(r, c - 1)
			return f1 and f2 and f3 and f4
		ans = 0
		for r in range(N):
			for c in range(M):
				if matrix[r][c] == 1 and (r, c) not in visited:
					if dfs(r, c):
						ans += 1
		return ans


class Solution:

	def closedIslands(self, matrix, N, M):

		def dfs(row, col):
			if row < 0 or row >= N or col < 0 or (col >= M):
				return False
			if matrix[row][col] == 0:
				return True
			if matrix[row][col] == -1:
				return True
			matrix[row][col] = -1
			is_closed = True
			for (dr, dc) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
				(new_row, new_col) = (row + dr, col + dc)
				is_closed &= dfs(new_row, new_col)
			return is_closed
		closed_islands = 0
		for row in range(N):
			for col in range(M):
				if matrix[row][col] == 1 and (row == 0 or row == N - 1 or col == 0 or (col == M - 1)):
					dfs(row, col)
		for row in range(N):
			for col in range(M):
				if matrix[row][col] == 1:
					if dfs(row, col):
						closed_islands += 1
		return closed_islands


class Solution:

	def closedIslands(self, matrix, N, M):

		def to_string(r, c):
			return str(r) + '-' + str(c)
		n_islands = 0
		cells = set()
		for row in range(N):
			for col in range(M):
				if matrix[row][col] and to_string(row, col) not in cells:
					is_closed = True
					current_island = set([to_string(row, col)])
					visited = [(row, col)]
					while visited:
						(r, c) = visited.pop()
						if is_closed:
							is_closed = r != 0 and r != N - 1 and (c != 0) and (c != M - 1)
						if r and matrix[r - 1][c] and (to_string(r - 1, c) not in current_island):
							current_island.add(to_string(r - 1, c))
							visited.append((r - 1, c))
						if r < N - 1 and matrix[r + 1][c] and (to_string(r + 1, c) not in current_island):
							current_island.add(to_string(r + 1, c))
							visited.append((r + 1, c))
						if c and matrix[r][c - 1] and (to_string(r, c - 1) not in current_island):
							current_island.add(to_string(r, c - 1))
							visited.append((r, c - 1))
						if c < M - 1 and matrix[r][c + 1] and (to_string(r, c + 1) not in current_island):
							current_island.add(to_string(r, c + 1))
							visited.append((r, c + 1))
					cells.update(current_island)
					n_islands += is_closed
		return n_islands


class Solution:

	def help(self, arr, i, j, N, M):
		if i < 0 or j < 0 or i == N or (j == M) or (arr[i][j] == 0):
			return
		arr[i][j] = 0
		self.help(arr, i + 1, j, N, M)
		self.help(arr, i - 1, j, N, M)
		self.help(arr, i, j + 1, N, M)
		self.help(arr, i, j - 1, N, M)

	def closedIslands(self, matrix, N, M):
		ans = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					if i == 0 or j == 0 or i == N - 1 or (j == M - 1):
						self.help(matrix, i, j, N, M)
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					ans += 1
					self.help(matrix, i, j, N, M)
		return ans


class Solution:

	def closedIslands(self, matrix, N, M):
		from functools import reduce
		visited = set()

		def dfs(r, c):
			if r >= N or r < 0 or c >= M or (c < 0):
				return False
			if matrix[r][c] == 0 or (r, c) in visited:
				return True
			visited.add((r, c))
			nbrs = [dfs(*arg) for arg in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]]
			return reduce(lambda acc, e: acc and e, nbrs, True)
		return sum([1 for r in range(N) for c in range(M) if matrix[r][c] == 1 and (r, c) not in visited and dfs(r, c)])


class Solution:

	def closedIslands(self, matrix, N, M):
		visited = set()

		def dfs(r, c):
			if r >= N or r < 0 or c >= M or (c < 0):
				return False
			if matrix[r][c] == 0:
				return True
			if (r, c) in visited:
				return True
			visited.add((r, c))
			a = dfs(r + 1, c)
			b = dfs(r - 1, c)
			c1 = dfs(r, c + 1)
			d = dfs(r, c - 1)
			return a and b and c1 and d
		ans = 0
		for r in range(N):
			for c in range(M):
				if matrix[r][c] == 1 and (r, c) not in visited:
					if dfs(r, c):
						ans += 1
		return ans


class Solution:

	def closedIslands(self, matrix, N, M):
		ok = True
		visited = set()

		def dfs(r, c):
			nonlocal ok, visited
			if r >= N or r < 0 or c >= M or (c < 0):
				ok = False
				return
			if matrix[r][c] == 0 or (r, c) in visited:
				return
			visited.add((r, c))
			dfs(r + 1, c)
			dfs(r - 1, c)
			dfs(r, c + 1)
			dfs(r, c - 1)
		ans = 0
		for r in range(N):
			for c in range(M):
				if matrix[r][c] == 1 and (r, c) not in visited:
					ok = True
					dfs(r, c)
					if ok:
						ans += 1
		return ans


class Solution:

	def isClosed(self, matrix, x, y, N, M):
		closed = 0
		if y > 0 and y < N - 1 and (matrix[y - 1][x] == 0) and (matrix[y + 1][x] == 0):
			if x > 0 and x < M - 1 and (matrix[y][x - 1] == 0) and (matrix[y][x + 1] == 0):
				closed = 1
		return closed

	def closedIslands_v1(self, matrix, N, M):
		closed = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					if self.isClosed(matrix, j, i, N, M):
						closed += 1
		return closed

	def DFS(self, matrix, i, j, N, M):
		if i < 0 or j < 0 or i == N or (j == M) or (matrix[i][j] == 0):
			return
		matrix[i][j] = 0
		self.DFS(matrix, i + 1, j, N, M)
		self.DFS(matrix, i - 1, j, N, M)
		self.DFS(matrix, i, j + 1, N, M)
		self.DFS(matrix, i, j - 1, N, M)

	def closedIslands(self, matrix, N, M):
		res = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					if i == 0 or j == 0 or i == N - 1 or (j == M - 1):
						self.DFS(matrix, i, j, N, M)
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					res += 1
					self.DFS(matrix, i, j, N, M)
		return res


class Solution:

	def closedIslands(self, matrix, N, M):
		delr = [-1, 0, 1, 0]
		delc = [0, 1, 0, -1]

		def dfs(i, j):
			matrix[i][j] = -1
			for _ in range(4):
				newr = i + delr[_]
				newc = j + delc[_]
				if newr >= 0 and newr < N and (newc >= 0) and (newc < M) and (matrix[newr][newc] == 1):
					dfs(newr, newc)
		for i in range(M):
			if matrix[0][i] == 1:
				dfs(0, i)
			if matrix[N - 1][i] == 1:
				dfs(N - 1, i)
		for i in range(N):
			if matrix[i][0] == 1:
				dfs(i, 0)
			if matrix[i][M - 1] == 1:
				dfs(i, M - 1)
		ans = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					dfs(i, j)
					ans += 1
		return ans


from collections import deque

class Solution:

	def closedIslands(self, mat, N, M):
		visited = [[False] * M for _ in range(N)]
		check = lambda x, y: 0 <= x < N and 0 <= y < M
		moves = [[-1, 0], [0, -1], [1, 0], [0, 1]]

		def bfs(i, j):
			queue = deque([(i, j)])
			visited[i][j] = True
			while queue:
				(x, y) = queue.popleft()
				for (dx, dy) in moves:
					nex = x + dx
					ney = y + dy
					if check(nex, ney) and (not visited[nex][ney]) and mat[nex][ney]:
						visited[nex][ney] = True
						queue.append((nex, ney))
		for i in range(N):
			if not visited[i][M - 1] and mat[i][M - 1]:
				bfs(i, M - 1)
			if not visited[i][0] and mat[i][0]:
				bfs(i, 0)
		for i in range(M):
			if not visited[N - 1][i] and mat[N - 1][i]:
				bfs(N - 1, i)
			if not visited[0][i] and mat[0][i]:
				bfs(0, i)
		res = 0
		for i in range(1, N - 1):
			for j in range(1, M - 1):
				if mat[i][j] and (not visited[i][j]):
					res += 1
					bfs(i, j)
		return res


class Solution:

	def dfs(self, x, y, matrix, N, M):
		if x < 0 or y < 0 or x >= N or (y >= M) or (matrix[x][y] == 0):
			return
		matrix[x][y] = 0
		dx = [0, 1, 0, -1]
		dy = [1, 0, -1, 0]
		for i in range(4):
			self.dfs(x + dx[i], y + dy[i], matrix, N, M)

	def closedIslands(self, matrix, N, M):
		ans = 0
		for i in range(N):
			for j in range(M):
				if (i == 0 or j == 0 or i == N - 1 or (j == M - 1)) and matrix[i][j] == 1:
					self.dfs(i, j, matrix, N, M)
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					self.dfs(i, j, matrix, N, M)
					ans += 1
		return ans


class Solution:

	def dfs(self, i, j, N, M):
		if i < 0 or j < 0 or i == N or (j == M):
			return
		if not self.matrix[i][j]:
			return
		self.matrix[i][j] = 0
		self.dfs(i + 1, j, N, M)
		self.dfs(i - 1, j, N, M)
		self.dfs(i, j + 1, N, M)
		self.dfs(i, j - 1, N, M)

	def dfs1(self, i, j, N, M):
		if i < 0 or j < 0 or i == N or (j == M):
			return
		if not self.matrix[i][j]:
			return
		self.matrix[i][j] = 0
		self.dfs1(i + 1, j, N, M)
		self.dfs1(i - 1, j, N, M)
		self.dfs1(i, j + 1, N, M)
		self.dfs1(i, j - 1, N, M)

	def closedIslands(self, matrix, N, M):
		self.matrix = matrix
		for i in range(N):
			for j in range(M):
				if (i == 0 or j == 0 or i == N - 1 or (j == M - 1)) and self.matrix[i][j]:
					self.dfs(i, j, N, M)
		ans = 0
		for i in range(N):
			for j in range(M):
				if self.matrix[i][j]:
					self.dfs1(i, j, N, M)
					ans += 1
		return ans


class Solution:

	def closedIslands(self, matrix, N, M):

		def dfs(i, j, grid):
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] == 0):
				return
			grid[i][j] = 0
			dfs(i - 1, j, grid)
			dfs(i + 1, j, grid)
			dfs(i, j - 1, grid)
			dfs(i, j + 1, grid)
		for i in range(N):
			dfs(i, 0, matrix)
			dfs(i, M - 1, matrix)
		for j in range(1, M - 1):
			dfs(0, j, matrix)
			dfs(N - 1, j, matrix)
		c = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					dfs(i, j, matrix)
					c += 1
		return c


import queue

class Solution:

	def check(self, i, j, n, m, matrix):
		if i < 0 or j < 0 or i > n - 1 or (j > m - 1) or (not matrix[i][j]):
			return False
		matrix[i][j] = 0
		return True

	def bfs(self, i, j, n, m, matrix):
		q = queue.deque()
		q.append([i, j])
		while q:
			(i, j) = q.popleft()
			matrix[i][j] = 0
			if self.check(i + 1, j, n, m, matrix):
				q.append([i + 1, j])
			if self.check(i, j + 1, n, m, matrix):
				q.append([i, j + 1])
			if self.check(i - 1, j, n, m, matrix):
				q.append([i - 1, j])
			if self.check(i, j - 1, n, m, matrix):
				q.append([i, j - 1])

	def closedIslands(self, matrix, N, M):
		for i in range(N):
			if matrix[i][0] == 1:
				self.bfs(i, 0, N, M, matrix)
			if matrix[i][M - 1] == 1:
				self.bfs(i, M - 1, N, M, matrix)
		for j in range(M):
			if matrix[0][j] == 1:
				self.bfs(0, j, N, M, matrix)
			if matrix[N - 1][j] == 1:
				self.bfs(N - 1, j, N, M, matrix)
		ans = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					ans += 1
					self.bfs(i, j, N, M, matrix)
		return ans


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def closedIslands(self, mat, N, M):

		def dfs(i, j, l):
			if i == N or j == M or i < 0 or (j < 0):
				return
			if mat[i][j] == 0:
				return
			if i == N - 1 or j == M - 1 or i == 0 or (j == 0):
				l.append(1)
			mat[i][j] = 0
			dfs(i + 1, j, l)
			dfs(i, j + 1, l)
			dfs(i - 1, j, l)
			dfs(i, j - 1, l)
		count = 0
		for i in range(N):
			for j in range(M):
				if mat[i][j] == 1:
					l = []
					dfs(i, j, l)
					if len(l) == 0:
						count = count + 1
		return count


class Solution:

	def closedIslands(self, matrix, N, M):

		def dfs(i: int, j: int, G: list):
			stack = [(i, j)]
			while stack:
				(i, j) = stack.pop()
				if i < 0 or j < 0 or i >= len(G) or (j >= len(G[0])):
					continue
				if G[i][j] == 0:
					continue
				G[i][j] = 0
				stack.append((i + 1, j))
				stack.append((i, j + 1))
				stack.append((i - 1, j))
				stack.append((i, j - 1))
		n = N
		m = M
		G = matrix
		count = 0
		for i in range(n):
			for j in range(m):
				if i < 1 or j < 1 or i >= len(G) - 1 or (j >= len(G[0]) - 1 and G[i][j]):
					dfs(i, j, G)
		for i in range(n):
			for j in range(m):
				if G[i][j]:
					dfs(i, j, G)
					count += 1
		return count


class Solution:

	def closedIslands(self, matrix, N, M):

		def dfs(x, y):
			if x < 0 or x >= N or y < 0 or (y >= M) or (matrix[x][y] == 0):
				return
			matrix[x][y] = 0
			dfs(x + 1, y)
			dfs(x - 1, y)
			dfs(x, y + 1)
			dfs(x, y - 1)

		def fill(x, y):
			if x < 0 or x >= N or y < 0 or (y >= M) or (matrix[x][y] != 1):
				return
			matrix[x][y] = 0
			fill(x + 1, y)
			fill(x - 1, y)
			fill(x, y + 1)
			fill(x, y - 1)
		for i in range(N):
			fill(i, 0)
			fill(i, M - 1)
		for j in range(M):
			fill(0, j)
			fill(N - 1, j)
		count = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					dfs(i, j)
					count += 1
		return count


from collections import deque

class Solution:

	def closedIslands(self, matrix, N, M):

		def ispos(i, j, n, m):
			if i < 0 or i == n or j < 0 or (j == m):
				return False
			return True
		edges1 = [(0, i) for i in range(M)]
		edges2 = [(i, 0) for i in range(N)]
		edges3 = [(N - 1, i) for i in range(M)]
		edges4 = [(i, M - 1) for i in range(N)]
		all_edges = edges1 + edges2 + edges3 + edges4
		q = deque()
		visit = [[0] * M for _ in range(N)]
		for (r, c) in all_edges:
			if matrix[r][c] == 1:
				visit[r][c] = 1
				q.append((r, c))
		dic1 = [-1, 1, 0, 0]
		dic2 = [0, 0, -1, 1]
		while q:
			(r, c) = q.popleft()
			matrix[r][c] = 0
			for i in range(4):
				nr = r + dic1[i]
				nc = c + dic2[i]
				if ispos(nr, nc, N, M) and visit[nr][nc] == 0 and (matrix[nr][nc] == 1):
					q.append((nr, nc))
					visit[nr][nc] = 1
		visit1 = set()

		def bfs(i, j):
			q = deque()
			q.append((i, j))
			dic1 = [-1, 1, 0, 0]
			dic2 = [0, 0, -1, 1]
			visit1.add((i, j))
			while q:
				(r, c) = q.popleft()
				for i in range(4):
					nr = r + dic1[i]
					nc = c + dic2[i]
					if ispos(nr, nc, N, M) and (nr, nc) not in visit1 and (matrix[nr][nc] == 1):
						visit1.add((nr, nc))
						q.append((nr, nc))
		ans = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1 and (i, j) not in visit1:
					ans += 1
					bfs(i, j)
		return ans


class Solution:

	def closedIslands(self, matrix, N, M):
		dp = [[0 for i in range(M)] for j in range(N)]

		def check(dp, matrix, i, j, n, m):
			if i == 0 or j == 0 or i == n - 1 or (j == m - 1):
				if matrix[i][j] == 0:
					return True
				else:
					return False
			if dp[i][j] == 1:
				return True
			if matrix[i][j] == 0:
				return True
			else:
				dp[i][j] = 1
				a = check(dp, matrix, i + 1, j, n, m)
				b = check(dp, matrix, i - 1, j, n, m)
				c = check(dp, matrix, i, j - 1, n, m)
				d = check(dp, matrix, i, j + 1, n, m)
				return a and b and c and d
		cnt = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1 and dp[i][j] == 0:
					if check(dp, matrix, i, j, N, M) == True:
						cnt += 1
		return cnt


class Solution:

	def closedIslands(self, matrix, N, M):

		def dfs(i: int, j: int, grid: list):
			q = [(i, j)]
			while q:
				(i, j) = q.pop()
				if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])):
					continue
				if grid[i][j] == 0:
					continue
				grid[i][j] = 0
				q.append((i + 1, j))
				q.append((i, j + 1))
				q.append((i - 1, j))
				q.append((i, j - 1))
		n = N
		m = M
		grid = matrix
		ans = 0
		for i in range(n):
			for j in range(m):
				if i < 1 or j < 1 or i >= len(grid) - 1 or (j >= len(grid[0]) - 1 and grid[i][j]):
					dfs(i, j, grid)
		for i in range(n):
			for j in range(m):
				if grid[i][j]:
					dfs(i, j, grid)
					ans += 1
		return ans


from collections import deque

class Solution:

	def closedIslands(self, matrix, N, M):

		def help(arr, i, j, N, M):
			if i < 0 or j < 0 or i == N or (j == M) or (arr[i][j] == 0):
				return
			arr[i][j] = 0
			help(arr, i + 1, j, N, M)
			help(arr, i - 1, j, N, M)
			help(arr, i, j + 1, N, M)
			help(arr, i, j - 1, N, M)
		ans = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					if i == 0 or j == 0 or i == N - 1 or (j == M - 1):
						help(matrix, i, j, N, M)
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					ans += 1
					help(matrix, i, j, N, M)
		return ans


class Solution:

	def closedIslands(self, matrix, N, M):
		if not matrix or not matrix[0]:
			return 0
		closed_island_count = 0

		def dfs(i, j):
			if i < 0 or i >= N or j < 0 or (j >= M) or (matrix[i][j] == 0):
				return
			matrix[i][j] = 0
			dfs(i + 1, j)
			dfs(i - 1, j)
			dfs(i, j + 1)
			dfs(i, j - 1)
		for j in range(M):
			dfs(0, j)
			dfs(N - 1, j)
		for i in range(N):
			dfs(i, 0)
			dfs(i, M - 1)
		for i in range(1, N - 1):
			for j in range(1, M - 1):
				if matrix[i][j] == 1:
					dfs(i, j)
					closed_island_count += 1
		return closed_island_count


class Solution:

	def closedIslands(self, matrix, N, M):
		for j in range(M):
			if matrix[0][j] == 1:
				self.dfs(0, j)
			if matrix[N - 1][j] == 1:
				self.dfs(N - 1, j)
		for i in range(N):
			if matrix[i][0] == 1:
				self.dfs(i, 0)
			if matrix[i][M - 1] == 1:
				self.dfs(i, M - 1)
		count = 0
		for i in range(1, N):
			for j in range(1, M):
				if matrix[i][j] == 1:
					self.dfs(i, j)
					count += 1
		return count

	def dfs(self, i, j):
		if not (0 <= i < N and 0 <= j < M and (matrix[i][j] == 1)):
			return
		matrix[i][j] = 0
		self.dfs(i - 1, j)
		self.dfs(i, j - 1)
		self.dfs(i + 1, j)
		self.dfs(i, j + 1)


class Solution:

	def closedIslands(self, matrix, N, M):

		def submergeIsland(r, c):
			if r < 0 or r >= N or c < 0 or (c >= M):
				return
			matrix[r][c] = 0
			for (newr, newc) in [(r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)]:
				if 0 <= newr < N and 0 <= newc < M and (matrix[newr][newc] == 1):
					matrix[newr][newc] = 0
					submergeIsland(newr, newc)
			return
		for i in range(N):
			if i == 0 or i == N - 1:
				for j in range(M):
					if matrix[i][j] == 1:
						submergeIsland(i, j)
			else:
				if matrix[i][0] == 1:
					submergeIsland(i, 0)
				if matrix[i][-1] == 1:
					submergeIsland(i, M - 1)
		ans = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					ans += 1
					submergeIsland(i, j)
		return ans


from collections import deque

class Solution:

	def closedIslands(self, matrix, N, M):
		visited = [[0] * M for _ in range(N)]
		q = deque()

		def isValid(i, j, visited):
			return True if 0 <= i < N and 0 <= j < M and (visited[i][j] == 0) and (matrix[i][j] == 1) else False

		def bfs(q, visited):
			while q:
				(x, y) = q.popleft()
				for (a, b) in ([x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]):
					if isValid(a, b, visited):
						visited[a][b] = 1
						q.append([a, b])
		ans = 0
		for i in range(N):
			for j in range(M):
				if i == 0 or i == N - 1 or j == 0 or (j == M - 1):
					if matrix[i][j] == 1:
						q.append([i, j])
						visited[i][j] = 1
						bfs(q, visited)
		for i in range(N):
			for j in range(M):
				if visited[i][j] == 0 and matrix[i][j] == 1:
					ans += 1
					q.append([i, j])
					bfs(q, visited)
		return ans


class Solution:

	def closedIslands(self, matrix, N, M):
		self.res = True

		def canWePlace(i, j, row, col):
			if i >= row or j >= col or i < 0 or (j < 0):
				self.res = False
				return False
			if matrix[i][j] == 1:
				matrix[i][j] = 0
				canWePlace(i + 1, j, row, col)
				canWePlace(i, j + 1, row, col)
				canWePlace(i, j - 1, row, col)
				canWePlace(i - 1, j, row, col)
			else:
				return True
			return self.res
		result = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j] == 1:
					val = canWePlace(i, j, N, M)
					if val:
						result += 1
					else:
						self.res = True
		return result


class Solution:

	def get_no_of_islands(self, matrix, x, y, N, M):
		res = 1
		if x == 0 or x == N - 1 or y == 0 or (y == M - 1):
			res = float('inf')
		matrix[x][y] = 0
		dx = [0, 0, 1, -1]
		dy = [1, -1, 0, 0]
		for i in range(4):
			if self.isValid(x + dx[i], y + dy[i], matrix, N, M):
				res += self.get_no_of_islands(matrix, x + dx[i], y + dy[i], N, M)
		return res

	def closedIslands(self, matrix, N, M):
		res = 0
		for i in range(N):
			for j in range(M):
				if matrix[i][j]:
					cur_res = self.get_no_of_islands(matrix, i, j, N, M)
					if cur_res != float('inf'):
						res += 1
		return res

	def isValid(self, x, y, matrix, N, M):
		if x == -1 or y == -1 or x == N or (y == M):
			return False
		return matrix[x][y] == 1


class Solution:

	def dfs(self, matrix, x, y):
		matrix[x][y] = 0
		(n, m) = (len(matrix), len(matrix[0]))
		ret = True
		for (nx, ny) in [(x, y + 1), (x, y - 1), (x - 1, y), (x + 1, y)]:
			if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny]:
				ret = ret and 0 < nx < n - 1 and (0 < ny < m - 1)
				if not self.dfs(matrix, nx, ny):
					ret = False
		return ret

	def closedIslands(self, matrix, N, M):
		return sum([self.dfs(matrix, i, j) for i in range(1, N - 1) for j in range(1, M - 1) if matrix[i][j]], 0)


class Solution:

	def closedIslands(self, grid, rows, cols):
		count = 0

		def dfs(i, j):
			if i < 0 or j < 0 or i >= rows or (j >= cols):
				return False
			if grid[i][j] == 0:
				return True
			grid[i][j] = 0
			left = dfs(i, j - 1)
			right = dfs(i, j + 1)
			up = dfs(i - 1, j)
			down = dfs(i + 1, j)
			return left and right and up and down
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] == 1 and dfs(i, j):
					count += 1
		return count


class Solution:

	def closedIslands(self, matrix, N, M):

		def dfs(row: int, col: int, grid: list):
			stack = [(row, col)]
			while stack:
				(r, c) = stack.pop()
				if r < 0 or c < 0 or r >= len(grid) or (c >= len(grid[0])):
					continue
				if grid[r][c] == 0:
					continue
				grid[r][c] = 0
				stack.append((r + 1, c))
				stack.append((r, c + 1))
				stack.append((r - 1, c))
				stack.append((r, c - 1))
		num_rows = N
		num_cols = M
		grid = matrix
		island_count = 0
		for i in range(num_rows):
			for j in range(num_cols):
				if i < 1 or j < 1 or i >= len(grid) - 1 or (j >= len(grid[0]) - 1 and grid[i][j]):
					dfs(i, j, grid)
		for i in range(num_rows):
			for j in range(num_cols):
				if grid[i][j]:
					dfs(i, j, grid)
					island_count += 1
		return island_count


class Solution:

	def dfs(self, row, col, mat):
		mat[row][col] = 0
		if row < len(mat) - 1 and mat[row + 1][col] == 1:
			self.dfs(row + 1, col, mat)
		if row > 0 and mat[row - 1][col] == 1:
			self.dfs(row - 1, col, mat)
		if col < len(mat[0]) - 1 and mat[row][col + 1] == 1:
			self.dfs(row, col + 1, mat)
		if col > 0 and mat[row][col - 1] == 1:
			self.dfs(row, col - 1, mat)

	def closedIslands(self, mat, n, m):
		for i in range(n):
			for j in range(m):
				if (i == n - 1 or i == 0) or (j == m - 1 or j == 0):
					if mat[i][j] == 1:
						self.dfs(i, j, mat)
		count = 0
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 1:
					count += 1
					self.dfs(i, j, mat)
		return count