Java实现 LeetCode 827 最大人工岛（DFS+暴力模拟）

Celandine ·

更新时间:2024-09-20

· 944 次阅读

827. 最大人工岛

在二维地图上， 0代表海洋， 1代表陆地，我们最多只能将一格 0 海洋变成 1变成陆地。

进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）

示例 1:

输入: [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
示例 2:

输入: [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
示例 3:

输入: [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
说明:

1 <= grid.length = grid[0].length <= 50
0 <= grid[i][j] <= 1

PS：
DFS把岛屿拿出来，每个岛屿放上不同的标记
然后，把每个岛屿的面积放进数组存上，
然后再找每一个海洋，看看要是能把当前海洋变成陆地，组成的最大的面积是多少记录一下

class Solution {
     public int largestIsland(int[][] grid) {
        int[] map = new int[grid.length*grid[0].length/2+3];
        int index = 2;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    fullIsland(grid, i, j, index++);
                }
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j  0) {
                    map[grid[i][j]]++;
                }
            }
        }
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j  0 && (t1 = grid[i - 1][j]) > 1) {
                        t += map[t1];
                    }
                    if (i  1 && t2 !=t1) {
                        t += map[t2];
                    }
                    if (j > 0 && (t3 = grid[i][j - 1]) > 1 && t2 !=t3 && t1 !=t3) {
                        t += map[t3];
                    }
                    if (j  1 && t4 != t3 && t2 != t4 && t1 != t4) {
                        t += map[t4];
                    }
                    max = Math.max(max, t);
                }
            }
        }
        if (max == 0) {
            if (grid[0][0] == 0) {
                return 1;
            } else {
                return grid.length*grid[0].length;
            }
        }
        return max;
    }
    public void fullIsland(int[][] grid, int i, int j, int index) {
        grid[i][j] = index;
        if (i > 0 && grid[i - 1][j] == 1) {
            fullIsland(grid, i - 1, j, index);
        }
        if (i  0 && grid[i][j - 1] == 1) {
            fullIsland(grid, i, j - 1, index);
        }
        if (j < grid[0].length - 1 && grid[i][j + 1] == 1) {
            fullIsland(grid, i, j + 1, index);
        }
    }
}