827. 最大人工岛

原题链接：
完成情况：
解题思路：
参考代码：
错误经验吸取

原题链接：

在这里插入图片描述

827. 最大人工岛

https://leetcode.cn/problems/making-a-large-island/description/

完成情况：

在这里插入图片描述

解题思路：

在这里插入图片描述

这段代码是一个解决问题的Java类。代码包含两个主要方法：

dfs(int[][] grid, int row, int col, int mark): 这是一个深度优先搜索方法，用于遍历矩阵数组中的区域。它会将当前遍历的节点标记为指定的标记，然后递归地查找与当前节点相邻的未标记节点，并统计当前区域内值为1的数量。
largestIsland(int[][] grid): 这是计算最大岛屿面积的方法。它遍历整个矩阵数组，将每个岛屿区域的大小存储在HashMap中。然后，对于每个为0的位置，计算将其变为1后所能扩展的新区域的大小，并找出最大的区域面积。

代码中的关键点包括：

使用position数组表示四个方向的移动。
使用mark变量来标记区域。
使用HashMapgetSize存储不同区域的大小。
使用HashSethashSet来避免重复计算相同区域。

最终返回最大的岛屿面积。如果矩阵数组中不存在0（即全为有效区域），则返回数组大小的平方。

参考代码：

package 代码随想录.图论;import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;public class _827最大人工岛 {int position[][] = {{1,0},{-1,0},{0,1},{0,-1}};/*** 只变一个格子，问能够形成的最大人工湖面积* 1 <= n <= 500，，，即允许重复访问* @param grid* @return*/public int largestIsland(int[][] grid) {/*首先需要知道当前状态下，每个独立岛屿的面积是多少，也就是说，除了本身的[row,col]之外，我们还需要记录[area]面积每一个位置去进行遍历一次，先判断是否存在是岛屿的位置上，然后++然后那个位置向四周均不为岛屿节点的节点去进行尝试填充，每一个填充点，再去判别是否可以去其他岛屿相连接，连接增加面积就是一开始需要记住的[area]*/int result = 0,markArea = 2,rowSize = grid.length,columnSize = grid[0].length;  //只要有节点存在，最小面积也是2Map<Integer, Integer> getAreaMap = new HashMap<Integer, Integer>();for (int row = 0; row < rowSize ;row++){for (int col = 0;col < columnSize;col++){if (grid[row][col] == 1){//先遍历一遍，给各个岛屿赋予初始面积int areaSize = 1 + dfs_largestIsland(grid,row,col,markArea);getAreaMap.put(markArea++,areaSize);}}}//----------------------------------------------------------------------for (int row = 0;row < rowSize;row++){for (int col = 0;col < columnSize;col++){if (grid[row][col] != 0)    continue;//防止重复计算，采用Set进行存储Set<Integer> hashSet = new HashSet<Integer>();//计算从当前位置开始获取的1的数量，初始化1，是因为把当前位置的0转换成了1int curSize = 1;for (int [] current : position){int curRow = row + current[0],curCol = col + current[1];//边界情况下就不能向外延伸了if (curRow < 0 || curRow >= grid.length || curCol < 0 || curCol >= grid[0].length)  continue;int curMark = grid[curRow][curCol];     //获取对应位置的标记//判别此节点是否已经被访问过if (hashSet.contains(curMark) || !getAreaMap.containsKey(curMark))  continue;//否则就加入，并且添加那个节点所对应的面积hashSet.add(curMark);curSize += getAreaMap.get(curMark);}result = Math.max(result,curSize);}}return result;//return result == 0 ? rowSize*columnSize : result;}/**** @param grid* @param row* @param col* @param markArea* @return*/private int dfs_largestIsland(int[][] grid, int row, int col, int markArea) {int res = 0;grid[row][col] = markArea;for (int [] current :position){int curRow = row + current[0],curCol = col + current[1];if (curRow < 0 || curRow >= grid.length || curCol < 0 || curCol >= grid.length) continue;if (grid[curRow][curCol] == 1){//给区域标记上面积res += dfs_largestIsland(grid,curRow,curCol,markArea)+1;}}return res;}
}