【数组】最大人工岛

题目描述

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？

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

示例 1:

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

解题思路 

将每个区块进行编号，并且把每个编号的面积存储到MAP中；遍历grid，如果grid[i][j]==0, 则check是否有有相连的编号，并且将所有编号的面积加起来，取最大值。

• 构造一个MAP map = new HashMap();
• 使用dfs遍历每个位置，并且更新每个位置的值，规则int tag = start + i * grid.length + j ; 计算每个小岛的面积S，并且设置map.put(tag, S);
• 从0到grid.length * grid.length 进行遍历，令max 设置成 map中的最大值； 
  • 如果grid[i][j]==0，则计算4个方向加起来的面积为res；
  • 计算最大的面积，max = Math.max(res,max);
• 返回max；

代码实现

import java.util.HashSet;
import java.util.Set;
 
class Solution {
 
    int[][] direct = new int[][]{
            {1, 0}, {-1, 0}, {0, 1}, {0, -1}
    };
 
    public int largestIsland(int[][] grid) {
        // 默认启动位置设置成2
        int start = 2;
 
        int map[] = new int[start + grid.length * grid[0].length];
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    int tag = start + i * grid.length + j;
                    grid[i][j] = tag;
                    int v = 1 + dfs(grid, tag, i, j);
                    max = Math.max(max, v);
                    map[tag] = v;
                }
            }
        }
 
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 0) {
                    Set set = new HashSet<>();
                    int res = 0;
                    for (int[] d : direct) {
                        int y = i + d[0];
                        int x = j + d[1];
                        if (y < grid.length && y >= 0 && x < grid[i].length && x >= 0 && grid[y][x] >= start) {
                            if (!set.contains(grid[y][x])) {
                                set.add(grid[y][x]);
                                res += map[(grid[y][x])];
                            }
                        }
                    }
                    max = Math.max(max, res + 1);
                }
            }
        }
 
        return max;
 
    }
 
    private int dfs(int[][] grid, int tag, int i, int j) {
 
        int res = 0;
        for (int[] d : direct) {
            int y = i + d[0];
            int x = j + d[1];
 
            if (y < grid.length && y >= 0 && x < grid[i].length && x >= 0 && grid[y][x] == 1) {
                grid[y][x] = tag;
                res += 1;
                res += dfs(grid, tag, y, x);
            }
        }
        return res;
    }
 
    public static void main(String[] args) {
        Solution solution = new Solution();
 
        System.out.println(solution.largestIsland(new int[][]{
                {1, 1, 0, 1},
                {1, 1, 0, 1},
                {0, 0, 0, 1},
                {1, 0, 1, 0}
        }));
    }
}

执行结果如下：

总结

这道题可以拆分成：1.使用DFS求解小岛面积、2.对每个小岛进行标记、3.求连通小岛的面积和。这道题我做了多次优化但是测试结果还是要67ms，欢迎有更加高效、简洁的思路回复。