最大人工岛

题目链接

最大人工岛

题目描述

注意 整个地图的长和宽相同，都是n1 <= n <= 500grid[i][j] 为 0 或 1 解答思路 如果使用原数组只能反映岛屿与海面的信息，还需要存储以下信息：整个岛的信息（要与其他岛作区分）以及整个岛的大小，方便后续判断海面中的某个位置是否连接着两个及以上不同的岛屿以及连接的岛屿的面积综上，需要使用一个相同的数组在遍历一次初始地图后存储岛屿信息，不同的岛屿用不同的编号表示，如第一个岛屿编号为2，第二个为3，依次类推，同时，还需要使用一个map来保存岛屿对应的面积大小，key对应岛屿编号，value对应对于面积 代码

class Solution {
    int n;
    int number;
    // 存储每个岛的位置信息
    int[][] newGrid;
    // 存储每个岛的面积
    Map<Integer, Integer> map;

    public int largestIsland(int[][] grid) {
        number = 2;
        n = grid.length;
        map = new HashMap<>();
        newGrid = new int[n][n];
        int res = 0;

        // 将所有小岛的信息存储到map中
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 访问到某个岛的某处，找到整个岛的信息
                if (newGrid[i][j] == 0 && grid[i][j] == 1) {
                    int area = dfs(i, j, grid, number);
                    res = Math.max(area, res);
                    map.put(number, area);
                    number++;
                }
            }
        }

        // 找到某个海面的位置观察其上下左右四块的信息，如果能连通不同的小岛，则将其面积相加
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (newGrid[i][j] == 0) {
                    List<Integer> numberList = new ArrayList<>();
                    int connectArea = connectIsland(i - 1, j, grid, numberList) 
                    + connectIsland(i + 1, j, grid, numberList) 
                    + connectIsland(i, j - 1, grid, numberList) 
                    + connectIsland(i, j + 1, grid, numberList) + 1;
                    res = Math.max(connectArea, res);
                }
            }
        }
        return res;
    }

    // 判断该块是否为岛屿，如果是能否连接在一起
    public int connectIsland(int i, int j, int[][] grid, List<Integer> numberList) {
        if (i < 0 || j < 0 || i >= n || j >= n) {
            return 0;
        }
        int islandNumber = newGrid[i][j];
        if(islandNumber != 0  && !numberList.contains(islandNumber)) {
            numberList.add(islandNumber);
            return map.get(islandNumber);
        } else {
            return 0;
        }
    }

    // 深度优先搜索找到整个岛的信息
    public int dfs(int i, int j, int[][] grid, int number) {
        if (i < 0 || j < 0 || i >= n || j >= n) {
            return 0;
        }
        if (newGrid[i][j] == 0 && grid[i][j] == 1) {
            newGrid[i][j] = number;
            return dfs(i - 1, j, grid, number) 
            + dfs(i + 1, j, grid, number) 
            + dfs(i, j - 1, grid, number) 
            + dfs(i, j + 1, grid, number) + 1;
        } else {
            return 0;
        }
    }
}

关键点 使用两种额外的数据结构保存岛屿信息，一个是数组使用不同编号保存整个岛屿，一个是map保存相应岛屿对应的面积