力扣每日一题2022-02-12中等题：飞地的数量

题目描述思路

DFS

Java实现Python实现

飞地的数量

根据题意，如果从一个陆地单元格无法移动到网格边界，则这个陆地单元格是飞地。则与边界相连的陆地单元格都不是飞地，不直接相连的单元格才可能是飞地。
因此可以从网格边界的每个陆地单元格开始深度优先搜索，遍历完之后，所有与网格边界相连的陆地单元格都被访问过了。然后遍历整个网格，如果网格中的一个陆地单元格没有被访问过，则该陆地单元格不和网格边界相连，是飞地。

class Solution {
    
    public static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    private int m, n;
    private boolean[][] visited;
    
    public int numEnclaves(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n-1);
        }
        for (int j = 1; j < n-1; j++) {
            dfs(grid, 0, j);
            dfs(grid, m-1, j);
        }
        int ans = 0;
        for (int i = 1; i < m-1; i++) {
            for (int j = 1; j < n-1; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    ans++;
                }
            }
        }
        return ans;
    }
    
    private void dfs(int[][] grid, int row, int col) {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0 || visited[row][col]) {
            return;
        }
        visited[row][col] = true;
        for (int[] dir: dirs) {
            dfs(grid, row + dir[0], col + dir[1]);
        }
    }
}

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        vis = [[False] * n for i in range(m)]
        
        def dfs(r, c):
            if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0 or vis[r][c]:
                return
            vis[r][c] = True
            for x, y in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                dfs(x, y)
        
        for i in range(m):
            dfs(i, 0)
            dfs(i, n-1)
        for j in range(1, n-1):
            dfs(0, j)
            dfs(m-1, j)
        return sum(grid[i][j] and not vis[i][j] for i in range(1, m - 1) for j in range(1, n - 1))