827. 最大人工岛

原题链接：

827. 最大人工岛

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

完成情况：

解题思路：

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

1. dfs(int[][] grid, int row, int col, int mark): 这是一个深度优先搜索方法，用于遍历矩阵数组中的区域。它会将当前遍历的节点标记为指定的标记，然后递归地查找与当前节点相邻的未标记节点，并统计当前区域内值为1的数量。

2. 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;  //只要有节点存在，最小面积也是2
        Map<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转换成了1
                int 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;
    }
}

错误经验吸取