2022-1-12DFSday5

题1:

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。

 

示例 1:

2022-1-12DFSday5
输入:grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出:6
解释:答案不应该是 11 ,因为岛屿只能包含水平或垂直这四个方向上的 1

示例 2:

输入:grid = [[0,0,0,0,0,0,0,0]]
输出:0

 

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] 为 0 或 1
 1 class Solution {
 2     int[][] dir={{-1,0},{1,0},{0,-1},{0,1}};
 3     int count;
 4     public int maxAreaOfIsland(int[][] grid) {
 5         int m=grid.length,n=grid[0].length;
 6         int ans=0;
 7         for (int i=0;i<m;i++){
 8             for (int j=0;j<n;j++){
 9                 if (grid[i][j]==1) {
10                     count=0;
11                     dfs(i,j,grid);
12                     ans=Math.max(ans,count);
13                 }
14             }
15         }
16         return ans;
17     }
18 
19     public void dfs(int x,int y,int[][] grid){
20         int m=grid.length,n=grid[0].length;
21         count++;
22         grid[x][y]=0;
23         for (int[] arr:dir){
24             int dx=x+arr[0];
25             int dy=y+arr[1];
26             if (dx>=0&&dx<m&&dy>=0&&dy<n&&grid[dx][dy]==1) {
27                 dfs(dx,dy,grid); 
28             }
29         }
30     }
31 }

思路:找到岛屿的同时计数,dfs结束的时候就可以得到面积。

题2:

1905. 统计子岛屿

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ,它们只包含 0 (表示水域)和 1 (表示陆地)。一个 岛屿 是由 四个方向 (水平或者竖直)上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

如果 grid2 的一个岛屿,被 grid1 的一个岛屿 完全 包含,也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含,那么我们称 grid2 中的这个岛屿为 子岛屿 。

请你返回 grid2 中 子岛屿 的 数目 。

 

示例 1:

2022-1-12DFSday5
输入: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]], 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]]
输出:3
解释:如上图所示,左边为 grid1 ,右边为 grid2 。
grid2 中标红的 1 区域是子岛屿,总共有 3 个子岛屿。

示例 2:

2022-1-12DFSday5
输入:grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
输出:2 
解释:如上图所示,左边为 grid1 ,右边为 grid2 。
grid2 中标红的 1 区域是子岛屿,总共有 2 个子岛屿。

 

提示:

  • m == grid1.length == grid2.length
  • n == grid1[i].length == grid2[i].length
  • 1 <= m, n <= 500
  • grid1[i][j] 和 grid2[i][j] 都要么是 0 要么是 1 。
 1 class Solution {
 2     public int countSubIslands(int[][] grid1, int[][] grid2) {
 3         int ans=0;
 4         int m=grid1.length,n=grid1[0].length;
 5         for (int i=0;i<m;i++){
 6             for (int j=0;j<n;j++)
 7             {
 8                 if (grid1[i][j]==0&&grid2[i][j]==1) dfs(grid2,i,j);
 9                 //如果grid1是海水,而grid2是岛屿,则这个岛屿不可能是子岛屿,淹掉
10             }
11         }
12         for (int i=0;i<m;i++){
13             for (int j=0;j<n;j++)
14             {
15                 //剩下的都是子岛屿
16                 if (grid2[i][j]==1) {
17                     dfs(grid2,i,j);
18                     ans++;
19                 }
20             }
21         }
22         return ans;
23     }
24 
25     public void dfs(int[][] grid,int x,int y){
26         int m=grid.length,n=grid[0].length;
27         if (x<0||y<0||x>=m||y>=n) return;
28         if (grid[x][y]==0) return;
29         grid[x][y]=0;
30         dfs(grid,x+1,y);
31         dfs(grid,x-1,y);
32         dfs(grid,x,y+1);
33         dfs(grid,x,y-1);
34     }
35 }

思路:先排除不可能是子岛屿的岛屿,再统计剩下的岛屿。

 

上一篇:【python教程入门学习】Python命令行参数


下一篇:Appium+python自动化(一)- 环境搭建—上(超详解)