Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land)
A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.
Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.
 
Example 1:
Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: 
There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.
Example 2:
Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: 
All 1s are either on the boundary or can reach the boundary.

 
Note:

1 <= A.length <= 500
1 <= A[i].length <= 500
0 <= A[i][j] <= 1
All rows have the same size.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Matrices

Data structures

Graph traversal

Spanning trees

Starter code: class Solution:
    def numEnclaves(self, A: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def numEnclaves(self, A: List[List[int]]) -> int:

		def dfs(i, j):
			if not (0 <= i < len(A) and 0 <= j < len(A[i])):
				return
			if A[i][j] == 0:
				return
			A[i][j] = 0
			dfs(i - 1, j)
			dfs(i + 1, j)
			dfs(i, j - 1)
			dfs(i, j + 1)
		for i in range(len(A)):
			for j in range(len(A[i])):
				if A[i][j] == 0:
					continue
				if i == 0 or j == 0 or i == len(A) - 1 or (j == len(A[i]) - 1):
					dfs(i, j)
		res = sum([sum(row) for row in A])
		return res


class Solution:

	def numEnclaves(self, A: List[List[int]]) -> int:
		dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		self.f = 0
		self.s = set()
		(m, n) = (len(A), len(A[0]))

		def rr(j, i):
			if (j, i) in self.s:
				return
			self.s.add((j, i))
			if A[j][i] == 0:
				return
			else:
				for d in dirs:
					j_new = d[0] + j
					i_new = d[1] + i
					if 0 <= j_new < m and 0 <= i_new < n:
						rr(j_new, i_new)
		for (j, row) in enumerate(A):
			for (i, v) in enumerate(row):
				if j == 0 or j == m - 1 or i == 0 or (i == n - 1):
					rr(j, i)
		f = 0
		for (j, row) in enumerate(A):
			for (i, v) in enumerate(row):
				if v == 1 and (j, i) not in self.s:
					f += 1
		return f


class Solution:

	def numEnclaves(self, A: List[List[int]]) -> int:
		grid = A
		if len(grid[0]) == 1:
			return 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.num_enclaves_helper(grid, [i, j])
		return sum((sum(row) for row in grid))

	def num_enclaves_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] == 0:
				return
		if grid[x][y] == 0:
			return
		grid[x][y] = 0
		self.num_enclaves_helper(grid, [x - 1, y])
		self.num_enclaves_helper(grid, [x + 1, y])
		self.num_enclaves_helper(grid, [x, y - 1])
		self.num_enclaves_helper(grid, [x, y + 1])
		return


class Solution:

	def dfs(self, A, i, j):
		if i < 0 or j < 0 or i >= len(A) or (j >= len(A[i])):
			return
		if A[i][j] == 0:
			return
		A[i][j] = 0
		self.dfs(A, i + 1, j)
		self.dfs(A, i - 1, j)
		self.dfs(A, i, j + 1)
		self.dfs(A, i, j - 1)

	def numEnclaves(self, A: List[List[int]]) -> int:
		if not A:
			return
		for row in range(len(A)):
			for col in range(len(A[row])):
				if row == 0 or row == len(A) - 1 or col == 0 or (col == len(A[row]) - 1 and A[row][col] == 1):
					self.dfs(A, row, col)
		count = 0
		for row in range(len(A)):
			for col in range(len(A[row])):
				if A[row][col] == 1:
					count += 1
		return count


class Solution:

	def numEnclaves(self, A: List[List[int]]) -> int:
		directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		area_of_enclaves = 0

		def traverse(x, y):
			area = 1
			A[x][y] = 0
			enclave = True
			for (x_direction, y_direction) in directions:
				new_x = x + x_direction
				new_y = y + y_direction
				if 0 <= new_x < len(A) and 0 <= new_y < len(A[0]):
					if A[new_x][new_y] == 1:
						(area_of_traverse, enclave_traverse) = traverse(new_x, new_y)
						area += area_of_traverse
						if not enclave_traverse:
							enclave = False
				else:
					enclave = False
			return (area, enclave)
		for (x, row) in enumerate(A):
			for (y, data) in enumerate(row):
				if data == 1:
					(area, enclave) = traverse(x, y)
					if enclave:
						area_of_enclaves += area
		return area_of_enclaves