1020.md

1020. Number of Enclaves

Solution 1 (time O(n), space O(n))

# DFS
class Solution(object):
    def numEnclaves(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m, n = len(grid), len(grid[0])
        vis = [[0 for _ in range(n)] for _ in range(m)]

        def dfs(x, y):
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                new_x = x + dx
                new_y = y + dy
                if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n:
                    continue
                if grid[new_x][new_y] == 0:
                    continue
                if vis[new_x][new_y] == 1:
                    continue
                vis[new_x][new_y] = 1
                dfs(new_x, new_y)

        for i in range(m):
            if grid[i][0] == 1 and vis[i][0] == 0:
                vis[i][0] = 1
                dfs(i, 0)
            if grid[i][n - 1] == 1 and vis[i][n - 1] == 0:
                vis[i][n - 1] = 1
                dfs(i, n - 1)
        for j in range(n):
            if grid[0][j] == 1 and vis[0][j] == 0:
                vis[0][j] = 1
                dfs(0, j)
            if grid[m - 1][j] == 1 and vis[m - 1][j] == 0:
                vis[m - 1][j] = 1
                dfs(m - 1, j)

        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and vis[i][j] == 0:
                    ans += 1
        return ans