LeetCode刷题系列 -- 1020. 飞地的数量

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1：

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
示例 2：

输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid[i][j] 的值为 0 或 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-enclaves
 

思路：

1. 遍历矩阵四个边界的元素，若是遇到 1 的格子，则以该格子做深度遍历。直到所有相邻的 （上、下、左、右）陆地单元格均为 0 为止
2. 遍历矩阵 grid，记录grid一共有多少个 1 ，即为题目所求
本题需要 图的深度遍历 dfs

java：

class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        
        boolean[][] visited = new boolean[m][n];
        
        // 左右边界
        for(int i=0;i<m;i++) {
            if(grid[i][0] == 1) {
                gridDfs(grid,i,0,visited);
            }
            if (grid[i][n-1] == 1) {
                gridDfs(grid,i,n-1,visited);
            }
        }
        
        // 上下边界
        for(int j=0;j<n;j++) {
            if(grid[0][j] == 1) {
                gridDfs(grid,0,j,visited);
            }
            if(grid[m-1][j] == 1) {
                gridDfs(grid,m-1,j,visited);
            }
        }
        int result = 0;
        
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j] == 1) {
                    result += 1;
                }
            }
        }
        
        return result;
    }
    
    public void gridDfs(int[][] grid,int i, int j, boolean[][] visited){
        if(i<0 || j<0 || i> grid.length-1 || j>grid[0].length-1) {
            return;
        }
        
        if(grid[i][j] == 0 || visited[i][j]) {
            return;
        }
        
        visited[i][j] = true;
        grid[i][j] = 0;
        
        gridDfs(grid,i-1,j,visited);
        gridDfs(grid,i,j-1,visited);
        gridDfs(grid,i+1,j,visited);
        gridDfs(grid,i,j+1,visited);
        
    }
}