网站开发是什么职业,网站域名空间管理,有什么做第二职业的网站吗,深圳联合办公空间❓ 1020. 飞地的数量
难度#xff1a;中等
给你一个大小为 m x n 的二进制矩阵 grid #xff0c;其中 0 表示一个 海洋单元格、1 表示一个 陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻#xff08;上、下、左、右#xff09;的陆地单元格或跨过 grid 的边…❓ 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.lengthn grid[i].length1 m, n 500grid[i][j] 的值为 0 或 1
思路DFS
本题要求找到不靠边的陆地面积那么
我们只要从周边找到陆地然后 通过 dfs 或者 bfs 将周边靠陆地且相邻的陆地都变成海洋然后再去重新遍历地图的时候统计此时还剩下的陆地就可以了。
代码(C、Java)
C
class Solution {
private:int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向int m 0, n 0;void dfs(int i, int j, vectorvectorint grid){if(grid[i][j] 0){ // 是海洋则返回return;}grid[i][j] 0;for(int k 0; k 4; k){ // 向四个方向遍历int nexti i dir[k][0];int nextj j dir[k][1];if(nexti 0 || nexti m || nextj 0 || nextj n) continue;dfs(nexti, nextj, grid);}}
public:int numEnclaves(vectorvectorint grid) {m grid.size();n grid[0].size();// 从左侧边和右侧边 向中间遍历for(int i 0; i m; i){dfs(i, 0, grid);dfs(i, n - 1, grid);}// 从上边和下边 向中间遍历for(int i 0; i n; i){dfs(0, i, grid);dfs(m - 1, i, grid);}//统计剩余陆地的面积int ans 0;for(int i 0; i m; i){for(int j 0; j n; j){if(grid[i][j] 1) ans;}}return ans;}
};Java
class Solution {private int[][] dir {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 四个方向int m 0, n 0;private void dfs(int i, int j, int[][] grid){if(grid[i][j] 0) return;// 是海洋则返回grid[i][j] 0;for(int k 0; k 4; k){// 向四个方向遍历int nexti i dir[k][0];int nextj j dir[k][1];// 超过边界if(nexti 0 || nexti m || nextj 0 || nextj n) continue;dfs(nexti, nextj, grid);}}public int numEnclaves(int[][] grid) {m grid.length;n grid[0].length;// 从左侧边和右侧边 向中间遍历for(int i 0; i m; i){dfs(i, 0, grid);dfs(i, n - 1, grid);}// 从上边和下边 向中间遍历for(int j 0; j n; j){dfs(0, j, grid);dfs(m - 1, j, grid);}//统计剩余陆地的面积int ans 0;for(int i 0; i m; i){for(int j 0; j n; j){if(grid[i][j] 1) ans;}}return ans;}
}运行结果 复杂度分析 时间复杂度 O ( m n ) O(mn) O(mn)其中m 和 n 分别是网格 grid 的行数和列数。深度优先搜索最多访问每个单元格一次需要 O ( m n ) O(mn) O(mn) 的时间遍历网格统计飞地的数量也需要 O ( m n ) O(mn) O(mn) 的时间。 空间复杂度 O ( m n ) O(mn) O(mn)空间复杂度主要取决于递归调用栈空间最大空间复杂度是 O ( m n ) O(mn) O(mn)。
题目来源力扣。 放弃一件事很容易每天能坚持一件事一定很酷一起每日一题吧 关注我LeetCode主页 / CSDN—力扣专栏每日更新 注 如有不足欢迎指正
