827_最大人工岛

难度：困难

题目

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例

示例一：

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

示例二：

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

示例三：

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

提示

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 500
  • grid[i][j] 为 0 或 1

解题

基本思路是先计算出所有岛屿的面积，在所有的格子上标记出岛屿的面积。然后搜索哪个海洋格子相邻的两个岛屿面积最大，但是为了防止同一片陆地被计算多次，所以给每个陆地打上不同的标记。

先 DFS 求出各陆地面积，同时用不同标号标记不同的陆地

1
2
3
4
5
6
7
8
9
10
11
public int dfs(int[][] grid, int i, int j, int index){
  if (!isArea(grid,i,j) || grid[i][j]!=1){
    return 0;
  }
  grid[i][j] = index;
  return 1
    +dfs(grid,i-1,j,index)
    +dfs(grid,i+1,j,index)
    +dfs(grid,i,j-1,index)
    +dfs(grid,i,j+1,index);
}

然后遍历海洋，求出与其相连的最大陆地面积之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int plusArea(int[][] grid, int i, int j, Map<Integer,Integer> map){
  if (!isArea(grid,i,j) || grid[i][j]!=0){
    return 0;
  }
  int size = 0;
  // 用 set 去重，防止出现同一块陆地
  Set<Integer> set = new HashSet<>();
  if (isArea(grid,i-1,j)&& grid[i-1][j]>=2){
    set.add(grid[i-1][j]);
  }
  if (isArea(grid,i+1,j)&& grid[i+1][j]>=2){
    set.add(grid[i+1][j]);
  }
  if (isArea(grid,i,j-1)&& grid[i][j-1]>=2){
    set.add(grid[i][j-1]);
  }
  if (isArea(grid,i,j+1)&& grid[i][j+1]>=2){
    set.add(grid[i][j+1]);
  }
  for(int num:set){
    size += map.get(num);
  }
  // 加上自身这块
  size +=1;
  return size;
}

将代码组合起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public int largestIsland(int[][] grid){
  int ans = 0;
  int maxSize = 0;
  int index = 2;
  Map<Integer,Integer> map = new HashMap<>();
  // 遍历求陆地面积
  for (int i = 0; i < grid.length; i++) {
    for (int j = 0; j < grid[0].length; j++) {
      if (grid[i][j]==1){
        int size = dfs(grid,i,j,index);
        maxSize = Math.max(maxSize,size);
        map.put(index,size);
        index+=1;
      }
    }
  }
  // 遍历海洋，求相邻陆地面积最大的海洋
  int maxSea = 0;
  for (int i = 0; i < grid.length; i++) {
    for (int j = 0; j < grid[0].length; j++) {
      if (grid[i][j]==0){
        int sea = plusArea(grid,i,j,map);
        maxSea = Math.max(sea,maxSea);
      }
    }
  }
  // 可能没有海洋，返回最大值
  ans = Math.max(maxSize,maxSea);
  return ans;
}

public int dfs(int[][] grid, int i, int j, int index){
  if (!isArea(grid,i,j) || grid[i][j]!=1){
    return 0;
  }
  grid[i][j] = index;
  return 1
    +dfs(grid,i-1,j,index)
    +dfs(grid,i+1,j,index)
    +dfs(grid,i,j-1,index)
    +dfs(grid,i,j+1,index);
}

public int plusArea(int[][] grid, int i, int j, Map<Integer,Integer> map){
  if (!isArea(grid,i,j) || grid[i][j]!=0){
    return 0;
  }
  int size = 0;
  // 用 set 去重，防止出现同一块陆地
  Set<Integer> set = new HashSet<>();
  if (isArea(grid,i-1,j)&& grid[i-1][j]>=2){
    set.add(grid[i-1][j]);
  }
  if (isArea(grid,i+1,j)&& grid[i+1][j]>=2){
    set.add(grid[i+1][j]);
  }
  if (isArea(grid,i,j-1)&& grid[i][j-1]>=2){
    set.add(grid[i][j-1]);
  }
  if (isArea(grid,i,j+1)&& grid[i][j+1]>=2){
    set.add(grid[i][j+1]);
  }
  for(int num:set){
    size += map.get(num);
  }
  // 加上自身这块
  size +=1;
  return size;
}

public boolean isArea(int[][] grid, int i, int j){
  return i>=0 && i<grid.length && j>=0 && j<grid[0].length;
}