一个网站的建设成本,嵌入式软件工程师前景,网络营销的具体方法,做公司网站员工保险统计子岛屿
题目描述
给你两个 m x n 的二进制矩阵 grid1 和 grid2 #xff0c;它们只包含 0 #xff08;表示水域#xff09;和 1 #xff08;表示陆地#xff09;。一个 岛屿 是由 四个方向 #xff08;水平或者竖直#xff09;上相邻的 1 组成的区域。任何矩阵以外…统计子岛屿
题目描述
给你两个 m x n 的二进制矩阵 grid1 和 grid2 它们只包含 0 表示水域和 1 表示陆地。一个 岛屿 是由 四个方向 水平或者竖直上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿被 grid1 的一个岛屿 完全 包含也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含那么我们称 grid2 中的这个岛屿为 子岛屿 。
请你返回 grid2 中 子岛屿 的 数目 。 思路
对于(i, j)来说有四种情况
case1:grid1[i][j] 1, grid2[i][j] 1.
case2:grid1[i][j] 1, grid2[i][j] 0.
case3: grid1[i][j] 0, grid2[i][j] 1.
case4: grid1[i][j] 0, grid2[i][j] 0.
对于case4我们完全不用关心剩下的case1、case2、case3我们再看由于是grid1包含grid2对于case3如果grid2是陆地grid1是海水那么grid1就不包含grid2那么我们就可以提前干掉grid2中的点对于case2如果grid1是陆地grid2是海水那么grid2必然不是grid1的子岛我们可以不做任何操作对于case1那么grid2必然是grid1的子岛我们就计数然后dfs。 下面看代码 public int countSubIslands(int[][] grid1, int[][] grid2) {int m grid1.length, n grid1[0].length, count 0;// 先排除不是子岛屿的节点for(int i 0;i m;i){for(int j 0;j n;j){if(grid2[i][j] 1 grid1[i][j] 0){dfs(grid2, i, j, m, n);}}}System.out.println();for(int i 0;i m;i){for(int j 0;j n;j){// 对于条件case1和case2来说// 这块可以优化成if(grid2[i][j] 1)if(grid2[i][j] 1 grid1[i][j] 1){count;dfs(grid2, i, j, m, n);}}}return count;}public void dfs(int[][] grid, int i, int j, int m, int n){if(i m || i 0 || j n || j 0|| grid[i][j] 0 ){return;}grid[i][j] 0;dfs(grid, i 1, j, m, n);dfs(grid, i - 1, j, m, n);dfs(grid, i, j 1, m, n);dfs(grid, i, j - 1, m, n);}public static void main(String[] args) {int[][] grid1 {{1,1,1,0,0},{0,1,1,1,1},{0,0,0,0,0},{1,0,0,0,0},{1,1,0,1,1}};int[][] grid2 {{1,1,1,0,0},{0,0,1,1,1},{0,1,0,0,0},{1,0,1,1,0},{0,1,0,1,0}};CountSubIslands countSubIslands new CountSubIslands();countSubIslands.countSubIslands(grid1, grid2);}
