You are given an n x m binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.
A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.
Find the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.
Example 1:
Input:
grid[][] = {{0, 0, 0, 0},
            {1, 0, 1, 0},
            {0, 1, 1, 0},
            {0, 0, 0, 0}}
Output:
3
Explanation:
0 0 0 0
1 0 1 0
0 1 1 0
0 0 0 0
The highlighted cells represents the land cells.
Example 2:
Input:
grid[][] = {{0, 0, 0, 1},
            {0, 1, 1, 0},
            {0, 1, 1, 0},
            {0, 0, 0, 1},
            {0, 1, 1, 0}}
Output:
4
Explanation:
0 0 0 1
0 1 1 0
0 1 1 0
0 0 0 1
0 1 1 0
The highlighted cells represents the land cells.
Your Task:
You don't need to print or input anything. Complete the function numberOfEnclaves() which takes a 2D integer matrix grid as the input parameter and returns an integer, denoting the number of land cells.
Expected Time Complexity: O(n * m)
Expected Space Complexity: O(n * m)
Constraints:
	1 <= n, m <= 500
	grid[i][j] == 0 or 1

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



from typing import List



class Solution:    

    def numberOfEnclaves(self, grid: List[List[int]]) -> int:

        # code here

Solutions:
from typing import List

class Solution:

	def numberOfEnclaves(self, grid: List[List[int]]) -> int:
		num_ones = 0
		ones = []
		visited = set()
		n = len(grid)
		m = len(grid[0])
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1:
					num_ones += 1
					if i == 0 or i == n - 1 or j == 0 or (j == m - 1):
						ones.append((i, j))
						visited.add((i, j))
		while ones:
			x = ones.pop(0)
			num_ones -= 1
			a1 = x[0]
			a2 = x[1]
			if a1 - 1 >= 0:
				if grid[a1 - 1][a2] == 1 and (a1 - 1, a2) not in visited:
					ones.append((a1 - 1, a2))
					visited.add((a1 - 1, a2))
			if a1 + 1 < n:
				if grid[a1 + 1][a2] == 1 and (a1 + 1, a2) not in visited:
					ones.append((a1 + 1, a2))
					visited.add((a1 + 1, a2))
			if a2 - 1 >= 0:
				if grid[a1][a2 - 1] == 1 and (a1, a2 - 1) not in visited:
					ones.append((a1, a2 - 1))
					visited.add((a1, a2 - 1))
			if a2 + 1 < m:
				if grid[a1][a2 + 1] == 1 and (a1, a2 + 1) not in visited:
					ones.append((a1, a2 + 1))
					visited.add((a1, a2 + 1))
		return num_ones


from typing import List
from collections import deque

class Solution:

	def numberOfEnclaves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		vis = [[0 for _ in range(m)] for _ in range(n)]
		queue = deque()
		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 grid[i][j] == 1:
						queue.append((i, j))
						vis[i][j] = 1
		delrow = [-1, 0, 1, 0]
		delcol = [0, 1, 0, -1]
		while queue:
			(row, col) = queue.popleft()
			for i in range(4):
				nrow = row + delrow[i]
				ncol = col + delcol[i]
				if 0 <= nrow < n and 0 <= ncol < m and (vis[nrow][ncol] == 0) and (grid[nrow][ncol] == 1):
					vis[nrow][ncol] = 1
					queue.append((nrow, ncol))
		res = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and vis[i][j] == 0:
					res += 1
		return res


from typing import List
from collections import deque

class Solution:

	def numberOfEnclaves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		r = [-1, 0, 1, 0]
		c = [0, 1, 0, -1]
		visited = [[0] * m for _ in range(n)]
		q = deque()
		for i in range(n):
			for j in range(m):
				if i == 0 or j == 0 or i == n - 1 or (j == m - 1):
					if grid[i][j] == 1:
						q.append([i, j])
						visited[i][j] = 1
		while q:
			[row, col] = q.popleft()
			for i in range(4):
				nrow = row + r[i]
				ncol = col + c[i]
				if nrow >= 0 and nrow < n and (ncol >= 0) and (ncol < m) and (visited[nrow][ncol] != 1) and (grid[nrow][ncol] == 1):
					visited[nrow][ncol] = 1
					q.append([nrow, ncol])
		count = 0
		for i in range(n):
			for j in range(m):
				if visited[i][j] != 1 and grid[i][j] == 1:
					count += 1
		return count


from typing import List
from collections import deque

class Solution:

	def numberOfEnclaves(self, grid: List[List[int]]) -> int:
		q = deque()
		n = len(grid)
		m = len(grid[0])
		visit = [[0] * m for _ in range(n)]
		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 grid[i][j] == 1:
					q.append((i, j))
					visit[i][j] = 1
		lis1 = [1, -1, 0, 0]
		lis2 = [0, 0, -1, 1]
		while q:
			(r, c) = q.pop()
			for i in range(4):
				nr = r + lis1[i]
				nc = c + lis2[i]
				if (nr >= 0 and nr < n and (nc >= 0) and (nc < m)) and grid[nr][nc] == 1 and (visit[nr][nc] == 0):
					visit[nr][nc] = 1
					q.append((nr, nc))
		ans = 0
		for i in range(1, n - 1):
			for j in range(1, m - 1):
				if grid[i][j] == 1 and visit[i][j] == 0:
					ans += 1
		return ans


import itertools
from collections import deque
from typing import List

class Solution:

	def numberOfEnclaves(self, grid: List[List[int]]) -> int:
		q = deque()
		n = len(grid)
		m = len(grid[0])
		visited = [[None for _ in range(m)] for _ in range(n)]
		delRow = [-1, 0, +1, 0]
		delCol = [0, +1, 0, -1]
		for (row, col) in itertools.product(range(n), range(m)):
			if row == n - 1 or row == 0 or col == 0 or (col == m - 1):
				if grid[row][col] == 1:
					q.append((row, col))
					visited[row][col] = 1
		while q:
			(newRow, newCol) = q.popleft()
			for i in range(4):
				nRow = newRow + delRow[i]
				nCol = newCol + delCol[i]
				if nRow >= 0 and nRow < n and (nCol >= 0) and (nCol < m) and (grid[nRow][nCol] == 1) and (visited[nRow][nCol] is None):
					visited[nRow][nCol] = 1
					q.append((nRow, nCol))
		count = 0
		for (row, col) in itertools.product(range(n), range(m)):
			if visited[row][col] == None and grid[row][col] == 1:
				count += 1
		return count


from typing import List
from collections import deque

class Solution:

	def numberOfEnclaves(self, grid: List[List[int]]) -> int:
		ROWS = len(grid)
		COLS = len(grid[0])
		queue = deque()
		for i in range(ROWS):
			for j in range(COLS):
				if i == 0 or i == ROWS - 1 or j == 0 or (j == COLS - 1 and grid[i][j] == 1):
					queue.append([i, j])
		while queue:
			(x, y) = queue.popleft()
			if grid[x][y] == 0:
				continue
			grid[x][y] = 0
			for (i, j) in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
				if 0 <= x + i < ROWS and 0 <= y + j < COLS and (grid[x + i][y + j] == 1):
					queue.append([x + i, y + j])
		ans = 0
		for i in range(ROWS):
			for j in range(COLS):
				if grid[i][j] == 1:
					ans += 1
		return ans


from typing import List
import collections

class Solution:

	def numberOfEnclaves(self, grid: List[List[int]]) -> int:
		visited = [[0 for i in range(len(grid[0]))] for j in range(len(grid))]
		n = len(grid)
		m = len(grid[0])
		queue = collections.deque([])
		for i in range(n):
			for j in range(m):
				if i == 0 or j == 0 or i == n - 1 or (j == m - 1):
					if visited[i][j] == 0 and grid[i][j] == 1:
						queue.append((i, j))
						visited[i][j] = 1
		while queue:
			(r, c) = queue.popleft()
			for (i, j) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
				if i + r >= 0 and i + r < n and (j + c >= 0) and (j + c < m) and (visited[i + r][j + c] == 0) and (grid[i + r][j + c] == 1):
					visited[i + r][j + c] = 1
					queue.append((i + r, j + c))
		count = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 1 and visited[i][j] == 0:
					count += 1
		return count


from typing import List
import sys

class Solution:

	def numberOfEnclaves(self, grid: List[List[int]]) -> int:
		sys.setrecursionlimit(10000)
		count = 0
		totalCount = 0
		x = len(grid)
		y = len(grid[0])
		for n in range(1, x - 1):
			for m in range(1, y - 1):
				count = 0
				if grid[n][m] == 1:
					grid[n][m] = 0
					count = self.checkNeighborElement(grid, n, m, x, y, 0)
					totalCount += count
		return totalCount

	def checkNeighborElement(self, grid, n, m, x, y, count):
		result = count + 1
		if self.validboundaries(n, m + 1, x, y):
			if grid[n][m + 1] == 1:
				grid[n][m + 1] = 0
				tempCount = self.checkNeighborElement(grid, n, m + 1, x, y, count)
				result = (tempCount + result, 0)[tempCount == 0 or result == 0]
		if self.validboundaries(n + 1, m, x, y):
			if grid[n + 1][m] == 1:
				grid[n + 1][m] = 0
				tempCount = self.checkNeighborElement(grid, n + 1, m, x, y, count)
				result = (tempCount + result, 0)[tempCount == 0 or result == 0]
		if self.validboundaries(n - 1, m, x, y):
			if grid[n - 1][m] == 1:
				grid[n - 1][m] = 0
				tempCount = self.checkNeighborElement(grid, n - 1, m, x, y, count)
				result = (tempCount + result, 0)[tempCount == 0 or result == 0]
		if self.validboundaries(n, m - 1, x, y):
			if grid[n][m - 1] == 1:
				grid[n][m - 1] = 0
				tempCount = self.checkNeighborElement(grid, n, m - 1, x, y, count)
				result = (tempCount + result, 0)[tempCount == 0 or result == 0]
		if n == 0 or m == 0 or n == x - 1 or (m == y - 1):
			return 0
		else:
			return result

	def validboundaries(self, n, m, x, y):
		if n >= 0 and n < x and (m >= 0) and (m < y):
			return True
		return False


from collections import deque
from typing import List

class Solution:

	def numberOfEnclaves(self, grid: List[List[int]]) -> int:
		m = len(grid)
		n = len(grid[0])
		vis = []
		for i in range(m):
			vis.append([0] * n)
		queue = deque([])
		for i in range(m):
			for j in range(n):
				if i == 0 or i == m - 1:
					if grid[i][j] == 1:
						vis[i][j] = 1
						queue.append((i, j))
				if j == 0 or j == n - 1:
					if grid[i][j] == 1:
						vis[i][j] = 1
						queue.append((i, j))
		while queue:
			(i, j) = queue.popleft()
			if i - 1 >= 0 and j >= 0 and (vis[i - 1][j] == 0) and (grid[i - 1][j] == 1):
				vis[i - 1][j] = 1
				queue.append((i - 1, j))
			if i >= 0 and j - 1 >= 0 and (vis[i][j - 1] == 0) and (grid[i][j - 1] == 1):
				vis[i][j - 1] = 1
				queue.append((i, j - 1))
			if i + 1 <= m - 1 and j <= n - 1 and (vis[i + 1][j] == 0) and (grid[i + 1][j] == 1):
				vis[i + 1][j] = 1
				queue.append((i + 1, j))
			if i <= m - 1 and j + 1 <= n - 1 and (vis[i][j + 1] == 0) and (grid[i][j + 1] == 1):
				vis[i][j + 1] = 1
				queue.append((i, j + 1))
		cnt = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] != vis[i][j]:
					cnt += 1
		return cnt


from typing import List

class Solution:

	def numberOfEnclaves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		m = len(grid[0])
		visited_matrix = [[0 for j in range(m)] for i in range(n)]
		queue = []
		for i in range(m):
			if grid[0][i] == 1 and visited_matrix[0][i] == 0:
				queue.append([0, i])
			if grid[n - 1][i] == 1 and visited_matrix[n - 1][i] == 0:
				queue.append([n - 1, i])
		for i in range(n):
			if grid[i][0] == 1 and visited_matrix[i][0] == 0:
				queue.append([i, 0])
			if grid[i][m - 1] == 1 and visited_matrix[i][m - 1] == 0:
				queue.append([i, m - 1])
		while queue:
			row = queue[0][0]
			col = queue[0][1]
			visited_matrix[row][col] = 1
			queue.pop(0)
			row_del = [-1, 1, 0, 0]
			col_del = [0, 0, -1, 1]
			for i in range(4):
				new_row = row + row_del[i]
				new_col = col + col_del[i]
				if new_row < n and new_col >= 0 and (new_row >= 0) and (new_col < m) and (visited_matrix[new_row][new_col] == 0) and (grid[new_row][new_col] == 1):
					visited_matrix[new_row][new_col] = 1
					queue.append([new_row, new_col])
		count = 0
		for i in range(n):
			for j in range(m):
				if visited_matrix[i][j] == 0 and grid[i][j] == 1:
					count = count + 1
		return count


from typing import List

class Solution:

	def numberOfEnclaves(self, a: List[List[int]]) -> int:
		n = len(a)
		m = len(a[0])
		q = []
		for i in range(n):
			if a[i][0] == 1:
				q.append((i, 0))
			if a[i][m - 1] == 1:
				q.append((i, m - 1))
		for j in range(m):
			if a[0][j] == 1:
				q.append((0, j))
			if a[n - 1][j] == 1:
				q.append((n - 1, j))
		while len(q) != 0:
			(i, j) = q.pop(0)
			a[i][j] = 0
			for k in [-1, 1]:
				if i + k >= 0 and i + k < n and (a[i + k][j] == 1):
					a[i + k][j] = 0
					q.append((i + k, j))
				if j + k >= 0 and j + k < m and (a[i][j + k] == 1):
					a[i][j + k] = 0
					q.append((i, j + k))
		ans = 0
		for i in range(n):
			for j in range(m):
				if a[i][j] == 1:
					ans += 1
		return ans