2022-1-22DFSday4

题1：

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

 1 class Solution {
 2     int ans;
 3     int[][] dir={{-1,0},{1,0},{0,-1},{0,1}};
 4     public int numIslands(char[][] grid) {
 5         int m=grid.length,n=grid[0].length;
 6         for (int i=0;i) {
 7             for (int j=0;j) {
 8                 if (grid[i][j]=='1') {
 9                     ans++;
10                     dfs(i,j,grid);
11                 }
12             }
13         }
14         return ans;
15     }
16 
17     public void dfs(int x,int y,char[][] grid){
18         grid[x][y]='0';
19         int m=grid.length,n=grid[0].length;
20         for (int[] arr:dir){
21             int dx=x+arr[0];
22             int dy=y+arr[1];
23             if (dx>=0&&dy>=0&&dx) dfs(dx,dy,grid);
24         }
25     }
26 }

思路：遍历节点，遇到岛屿答案加1，并通过dfs搜索岛屿连通的所有岛屿变为陆地。

题2：

1254. 统计封闭岛屿的数目

有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。

我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。

如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。

请返回封闭岛屿的数目。

示例 1：

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

示例 2：

输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1

示例 3：

输入：grid = [[1,1,1,1,1,1,1],
             [1,0,0,0,0,0,1],
             [1,0,1,1,1,0,1],
             [1,0,1,0,1,0,1],
             [1,0,1,1,1,0,1],
             [1,0,0,0,0,0,1],
             [1,1,1,1,1,1,1]]
输出：2

提示：

• 1 <= grid.length, grid[0].length <= 100
• 0 <= grid[i][j] <=1

 1 class Solution {
 2     int[][] dir={{-1,0},{1,0},{0,-1},{0,1}};
 3     boolean flag;
 4     public int closedIsland(int[][] grid) {
 5         int m=grid.length,n=grid[0].length;
 6         int ans=0;
 7         for (int i=0;i){
 8             for (int j=0;j){
 9                 if (grid[i][j]==0) {
10                     flag=true;
11                     dfs(i,j,grid);
12                     if (flag) {
13                         ans++;
14                         //System.out.println(i+" "+j);
15                     }
16                 }
17             }
18         }
19         return ans;
20     }
21 
22     public void dfs(int x,int y,int[][] grid){
23         int m=grid.length,n=grid[0].length;
24         if (flag&&(x==0||y==0||x==m-1||y==n-1)) flag=false;
25         grid[x][y]=1;
26         for (int[] arr:dir){
27             int dx=x+arr[0];
28             int dy=y+arr[1];
29             if (dx>=0&&dx=0&&dy) {
30                 dfs(dx,dy,grid); 
31             }
32         }
33     }
34 }

思路：只要岛屿不和边界接触，就是被包围的岛屿，只要在题1基础上判断每个岛屿是否与边界接触。

题3：

1020. 飞地的数量

给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。

移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。

返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1：

输入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释： 
有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

示例 2：

输入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：
所有 1 都在边界上或可以到达边界。

提示：

1. 1 <= A.length <= 500
2. 1 <= A[i].length <= 500
3. 0 <= A[i][j] <= 1
4. 所有行的大小都相同

 1 class Solution {
 2     int[][] dir={{-1,0},{1,0},{0,-1},{0,1}};
 3     boolean flag;
 4     int count;
 5     public int numEnclaves(int[][] grid) {
 6         int m=grid.length,n=grid[0].length;
 7         int ans=0;
 8         for (int i=0;i){
 9             for (int j=0;j){
10                 if (grid[i][j]==1) {
11                     flag=true;
12                     count=0;
13                     dfs(i,j,grid);
14                     if (flag) {
15                         ans+=count;
16                     }
17                 }
18             }
19         }
20         return ans;
21     }
22 
23     public void dfs(int x,int y,int[][] grid){
24         int m=grid.length,n=grid[0].length;
25         if (flag&&(x==0||y==0||x==m-1||y==n-1)) flag=false;
26         grid[x][y]=0;
27         count+=1;
28         for (int[] arr:dir){
29             int dx=x+arr[0];
30             int dy=y+arr[1];
31             if (dx>=0&&dx=0&&dy) {
32                 dfs(dx,dy,grid); 
33             }
34         }
35     }
36 }

思路：在题2的基础上，添加一个DFS的计数器，飞地就是封闭的岛屿的面积，因次判断是否是封闭的情况，决定ans是否加上计数器。

优化：将靠近边界的岛屿全部淹没，再遍历一遍，所有不为陆地的都为答案。

 1 class Solution {
 2     int[][] dir={{-1,0},{1,0},{0,-1},{0,1}};
 3     int ans=0;
 4     public int numEnclaves(int[][] grid) {
 5         int m=grid.length,n=grid[0].length;
 6         for (int j=0;j){
 7             if (grid[0][j]==1) dfs1(0,j,grid);
 8             if (grid[m-1][j]==1) dfs1(m-1,j,grid);
 9         }
10         for (int i=0;i){
11             if (grid[i][0]==1) dfs1(i,0,grid);
12             if (grid[i][n-1]==1) dfs1(i,n-1,grid);
13         }
14         //for (int[] arr:grid){
15         //    for (int x:arr) System.out.print(x+" ");
16         //    System.out.println("  ");
17         //}
18         for (int i=0;i){
19             for (int j=0;j){
20                 if (grid[i][j]==1) {
21                     ans++;
22                 }
23             }
24         }
25         return ans;
26     }
27 
28 
29     public void dfs1(int x,int y,int[][] grid){
30         int m=grid.length,n=grid[0].length;
31         grid[x][y]=0;
32         for (int[] arr:dir){
33             int dx=x+arr[0];
34             int dy=y+arr[1];
35             if (dx>=0&&dx=0&&dy) {
36                 dfs1(dx,dy,grid); 
37             }
38         }
39     }
40 }