827. 最大人工岛

题目链接

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

思路

计算最大人工岛面积之前，需要先计算出所有岛屿的面积，在所有的格子上标记出岛屿的面积（同一个岛屿的所有格子上标注出这些格子所连成的岛屿的面积！）。然后搜索哪个海洋格子相邻的两个岛屿面积最大。例如下图中红色方框内的海洋格子，上边、左边都与岛屿相邻，我们可以计算出它变成陆地之后可以连接成的岛屿面积为 7 + 1 + 2 = 10。

然而，这种做法可能遇到一个问题。如下图中红色方框内的海洋格子，它的上边、左边都与岛屿相邻，这时候连接成的岛屿面积难道是 7 + 1 + 7 = 15？显然不是。这两个 7 来自同一个岛屿，所以填海造陆之后得到的岛屿面积只有 8。

所以，如果要让算法正确，我们得能区分一个海洋格子相邻的两个7是不是来自同一个岛屿。那么，我们不能在方格中标记岛屿的面积，而应该标记岛屿的索引（下标），另外用一个数组记录每个岛屿的面积，如下图，这样我们就可以发现红色方框内的海洋格子，它的“两个”相邻的岛屿实际上是同一个。

解法

解法过程如下：

class Solution {
    public int largestIsland(int[][] grid) {
        int tar = 2;
        int area = 0;
        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) {
                    // 计算当前岛屿面积并且进行编号
                    area = dfs(grid, i, j, tar);
                    map.put(tar, area);
                    tar++;
                }
            }
        }
        // 没有岛屿
        if (map.size() == 0) {
            return 1;
        }
        
        // 初始化为第一个岛屿的面积，避免出现全是岛屿没有水的情况
        int maxArea = map.get(2);
        int [] dx = new int[] {-1, 1, 0, 0};
        int [] dy = new int[] {0, 0, -1, 1};
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 搜索当前位置上下左右是否有岛屿
                if (grid[i][j] == 0) {
                    area = 1;
                    Set<Integer> set = new HashSet<>();
                    for (int k = 0; k < 4; k++) {
                        int m = i + dx[k];
                        int n = j + dy[k];
                        if (m < 0 || m >= grid.length || n < 0 || n >= grid[0].length || grid[m][n] == 0) {
                            continue;
                        }
                        tar = grid[m][n];
                        // 去重，避免同一岛屿重复计算
                        if (set.contains(tar)) {
                            continue;
                        }
                        set.add(tar);
                        area += map.get(tar);
                    }
                    maxArea = Math.max(area, maxArea);
                }
            }
        }
        return maxArea;
    }

    public int dfs(int[][] grid, int i, int j, int tar) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
            return 0;
        }
        int area = 1;
        grid[i][j] = tar;
        area += dfs(grid, i - 1, j, tar);
        area += dfs(grid, i + 1, j, tar);
        area += dfs(grid, i, j - 1, tar);
        area += dfs(grid, i, j + 1, tar);
        return area;
    }
}