### 题目描述 给你一个大小为 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 ### 题目解答 #### 思路 根据题目意思，求与边界不相连的1号区域数量。因此遍历所有为1的区域，采用dfs的方式，记录该区域的面积，如果该区域有边界位置，那么这一整块区域都与边界相连；如果该区域都没有与边界相连，那么整个区域加入求得结果中。 - 采用now记录每次dfs中区域的面积，如果说发现有边界区域，则将now设置为-1，那么后面的就不再记录，now一直是-1。dfs结束之后，就知道该区域与边界相连，就不加入sum总和了。 - 每次访问一个格子，就将其置为0，代表访问过，之后就不再访问 **算法复杂度** m 和 n 分别是网格grid的行数和列数 时间复杂度：每个格子如果为0就不访问，为1的话就访问，复杂度$$O(mn)$$ 空间复杂度：取决于dfs栈的大小，最多栈的深度就是整个网格，因此空间复杂度$$O(mn)$$ #### 代码实现 ```java class Solution { public int now;// 每次dfs中相连区域面积 public int numEnclaves(int[][] grid) { int res = 0; for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ if(grid[i][j]==1){ now = 0; dfs(grid, i, j); if(now !=-1) res += now; } } } return res; } public void dfs(int[][] grid, int i, int j){ // 如果走出边界直接返回 if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return; // 到达边界位置，那么所有的都不计数为0 if(i == 0 || i == grid.length-1 || j == 0 || j == grid[0].length-1) now = -1; if(now != -1) now ++; grid[i][j] = 0; dfs(grid, i-1, j); dfs(grid, i+1, j); dfs(grid, i, j-1); dfs(grid, i, j+1); return; } } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复