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.

Difficulty: interview

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