最大人工岛

827. 最大人工岛 - 力扣（LeetCode）

给你一个大小为 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

第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积

第二步：在遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。

以如下图为例：

第一步，则遍历图，并将岛屿到编号和面积上的统计，过程如图所示：

遍历过的节点直接用编号覆盖，可以充当visited数组的作用

第二步：将比例到为0的节点变为1，同时加上周围岛屿的面积

此处需要用一个Set记录周边岛屿的面积是否被统计过，避免重复计算

class Solution {
    int[][] move = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    int area = 0;
    int mark = 1; //记录岛屿的编号，每次遍历一个岛屿，mark+1

    public int largestIsland(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        Map<Integer, Integer> map = new HashMap<>();


        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1){
                    area = 0; //每个岛屿的面积
                    mark ++; //每遍历一个岛屿，编号+1，岛屿编号从2开始
                    dfs(grid, i, j, mark); 
                    map.put(mark, area); //记录岛屿编号和面积的映射
                }
            }
        }


        int max_sum = 0;
        Set<Integer> set = new HashSet<>(); //标记访问过的岛屿
        for(int i = 0; i< n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 0){ //把0变成1，同时加上周围岛屿的面积
                    set.clear();
                    int sum = 1;
                    for(int k = 0; k < 4; k++){
                        int next_i = i + move[k][0];
                        int next_j = j + move[k][1];
                        if(next_i < 0 || next_j < 0 || next_i >= n || next_j >= m || grid[next_i][next_j] == 0){
                            continue;
                        }
                        int num = grid[next_i][next_j];
                        if(set.contains(num)){ //访问过的岛屿不再加入总面积
                            sum += map.get(num);
                            set.add(num); 
                        }
                    }
                    max_sum = Math.max(max_sum, sum);
                }

            }
        }
        return max_sum == 0 ?  m * n : max_sum;
    }

    public void dfs(int[][] grid, int x, int y, int mark){
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length){
            return;
        }
        if(grid[x][y] == 0 || grid[x][y] > 1){
            return;
        }
        grid[x][y] = mark;
        area ++;
        dfs(grid, x + 1, y, mark);
        dfs(grid, x , y + 1, mark);
        fs(grid, x - 1, y, mark);
        dfs(grid, x, y - 1, mark);
    }
}

时间复杂度：$O(n*n)$，需要遍历2次图