题目描述

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/making-a-large-island

解答详情

这是一道DFS+二维+着色的题目，难度为hard。近日在LeetCode上刷DFS相关题的时候遇到的，觉得挺不错的一题，说一下个人的思路和见解：

如果使用暴力法：对每个海域即二维数组为0的位置进行dfs算出岛屿最大值，还需要对其置1后恢复，比较麻烦且容易出错，并且时间复杂度上在LeetCode上是肯定超时的。

其实对于DFS的题来说，一般使用DFS+回溯就能够解决了，但这毕竟是hard题，对此本人使用着色的方法，即定义一个int类型全局变量；先对二维数组进行一次DFS，将不同岛屿进行着色区分并计算出填海前（将某个0变成1）的面积；定义一个全局变量Map用于存储每个岛屿的对应面积，即颜色为key，对应面积为value；对其进行第一次DFS后，所有岛屿完成了着色并计算出填海前的面积，此时再去寻找具有相邻岛屿的海域进行填海（将某个0变成1），从而得出最大岛屿面积。

class Solution {
    //全局Map，key着色，val岛屿面积
    private Map<Integer,Integer> islandAreaMap = new HashMap<>();

    //全局int，每个岛屿的用color值划分
    private int color = -1;

    public int largestIsland(int[][] grid) {
        int res = 0;
        int m = grid.length;
        //先对二维数据进行一次dfs，得出每个岛屿的面积
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < m ; j++){
                if(grid[i][j]==1){
                    color --;//用于区分不同岛屿
                    int area = dfs(grid,i,j);//通过dfs计算岛屿面积
                    islandAreaMap.put(color,area);
                    res = Math.max(res,area);
                }
            }
        }

        //寻找相邻岛屿，填海，找最大值
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < m ; j++){
                //使用Set标记相邻岛屿面积
                Set<Integer> islandAreaSet = new HashSet<>();
                //判断填海位置是否具有相邻岛屿，岛屿已被着色
                if(grid[i][j]==0){
                    if(i > 0 && grid[i-1][j]<0){
                        islandAreaSet.add(grid[i-1][j]);// 将岛屿颜色作为val
                    }
                    if(i < m-1 && grid[i+1][j]<0){
                        islandAreaSet.add(grid[i+1][j]);
                    }
                    if(j > 0 && grid[i][j-1]<0){
                        islandAreaSet.add(grid[i][j-1]);
                    }
                    if(j < m-1 && grid[i][j+1]<0){
                        islandAreaSet.add(grid[i][j+1]);
                    }
                }
                //计算填海后岛屿面积
                int area = 1;
                for(Integer islandColor : islandAreaSet){
                    area += islandAreaMap.getOrDefault(islandColor,0);
                }
                res = Math.max(res,area);
            }
        }

        return res;
    }

    private int dfs(int[][] grid,int i,int j){
        int m = grid.length;
        //异常退出
        if(i < 0 || j < 0 || i >= m || j >= m || grid[i][j] < 1){
            return 0;
        }
        //对同一岛屿进行着色
        if(grid[i][j]==1){
            grid[i][j] = color;
        }
        //计算岛屿面积，对垂直/水平分别进行DFS
        return 1+dfs(grid,i-1,j)+dfs(grid,i+1,j)+dfs(grid,i,j-1)+dfs(grid,i,j+1);
    }
}