题目描述
给你一个大小为 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);
}
}