银川网站建设那家好,商标设计网站排行,办公空间设计装修,长宁区网站建设开发6.飞地的数量
题目描述
给你一个大小为 m x n 的二进制矩阵 grid #xff0c;其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻#xff08;上、下、左、右#xff09;的陆地单元格或跨过 grid 的边界。
返回网格中 无法…6.飞地的数量
题目描述
给你一个大小为 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 没有被包围因为它在边界上。题目分析
1.题目分析
给定一个二进制矩阵 grid其中0表示海洋单元格1表示陆地单元格。
一次移动是指从一个陆地单元格走到另一个相邻的陆地单元格或者跨过矩阵边界。
要求找出在任意次数的移动中无法离开网格边界的陆地单元格数量。2.思路分析
--主要思路
使用深度优先搜索DFS来遍历所有的陆地单元格并标记与边界相连的陆地单元格。
维护两个全局变量 flag 和 spare分别用于标记每块岛屿是否靠海和记录每块岛屿的面积。
遍历整个二维网格对每个陆地单元格进行DFS处理统计无法跨越边界的方块数。--详细步骤
-初始化 count 为0用于表示无法跨越边界的方块数。
-遍历二维网格 grid 的每个单元格 (i, j)
-如果当前单元格为陆地grid[i][j] 1则调用 dfs 方法进行DFS处理。
-在 dfs 方法中
如果当前位置 (i, j) 超出边界或者是海洋grid[i][j] 0则返回。否则标记当前位置为已访问更新 spare 记录当前岛屿面积。
如果当前位置在边界上则将 flag 标记为1表示当前岛屿靠近海洋。继续递归调用DFS处理当前位置的四个相邻位置。
如果当前岛屿不靠近海洋flag 0则将当前岛屿的面积累加到 count 中。最后返回 count 作为结果。
-复杂度分析
时间复杂度O(m*n)m 和 n 分别为二维网格的行数和列数需要遍历整个二维网格。
空间复杂度O(1)除了函数调用栈外没有使用额外空间。Java代码实现
class Solution {int flag 0; // 用于标记每块岛屿是否靠海int spare 0; // 用于标记每块岛屿的面积public int numEnclaves(int[][] grid) {int count 0; // 表示无法跨越边界的方块数for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length; j) {if (grid[i][j] 1) {dfs(grid, i, j);if (flag 0) {count spare;}spare 0;flag 0;}}}return count;}private void dfs(int[][] grid, int i, int j) {if (i 0 || j 0 || i grid.length || j grid[0].length) {return;}if (grid[i][j] 0) {return;}spare;grid[i][j] 0;if (i 0 || i grid.length - 1 || j 0 || j grid[0].length - 1) {flag 1; // 表示存在临海区域}dfs(grid, i 1, j); // 下dfs(grid, i - 1, j); // 上dfs(grid, i, j 1); // 右dfs(grid, i, j - 1); // 左}
}
