岛屿面积问题

岛屿面积问题

1、求岛屿面积或最大面积

一般解法是深度搜索，递归4个方向，统计每个岛的面积。

class Solution {
    private static final int[][] DIRS = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

    private int dfs(int[][] grid, int i, int j) {
        int area = 0;
        int m = grid.length;
        int n = grid[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return area;
        }
        if (grid[i][j] != 1) {
            return area;
        }
        grid[i][j] = 2;
        // 当前是土地格子，面积+1
        ++area;
        for (int[] d : DIRS) {
            area += dfs(grid, i + d[0], j + d[1]);
        }
        return area;
    }

    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (1 == grid[i][j]) {
                    ans = Math.max(ans, dfs(grid, i, j));
                }
            }
        }
        return ans;
    }
}

2、最大人工岛屿

就是有一次机会将一个格子填充土地，再判断最大岛屿面积。

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

思路：

1. dfs初始化，统计每个岛屿（带编号）面积，记录到hash表；

2. 再遍历水域格子，尝试填充成土地，计算相邻岛屿总面积，注意去重；

class Solution {
    private static final int[][] DIRS = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

    private Map<Integer, Integer> idToAreaMap = new HashMap<>();

    public int largestIsland(int[][] grid) {
        int ans = 0;
        int m = grid.length;
        int n = grid[0].length;

        // 先初始化
        init(grid);

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 遍历每个水域格子，尝试变成土地
                if (0 == grid[i][j]) {
                    List<Integer> islandIds = new ArrayList<>();
                    for (int[] d : DIRS) {
                        int x = i + d[0];
                        int y = j + d[1];
                        if (isValidIdx(m, n, x, y) && grid[x][y] >= 2) {
                            islandIds.add(grid[x][y]);
                        }
                    }
                    int sum = islandIds.stream()
                            .distinct()
                            .map(idToAreaMap::get)
                            .mapToInt(Integer::intValue)
                            .sum();
                    // sum+1就是变化后的总面积
                    ans = Math.max(ans, sum + 1);
                }
            }
        }
        // 如果ans为0，说明全是陆地
        return ans == 0 ? m * n : ans;
    }

    private void init(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 岛屿编码从2开始
        int id = 2;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (1 == grid[i][j]) {
                    int area = dfs(grid, i, j, id);
                    idToAreaMap.put(id, area);
                    ++id;
                }
            }
        }
    }

    private int dfs(int[][] grid, int i, int j, int id) {
        int area = 0;
        int m = grid.length;
        int n = grid[0].length;
        if (!isValidIdx(m, n, i, j)) {
            return area;
        }
        if (grid[i][j] != 1) {
            return area;
        }
        // id表示当前岛屿的编号
        grid[i][j] = id;
        // 当前是土地格子，面积+1
        ++area;
        for (int[] d : DIRS) {
            area += dfs(grid, i + d[0], j + d[1], id);
        }
        return area;
    }

    private boolean isValidIdx(int m, int n, int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
}

3、总结

基本就是DFS的讨论，但是注意边界、避免重复访问、环形岛屿这些。。。