岛屿问题

遍历框架

public void solve(char[][] grid) {
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
            }
        }
    }
}

public void dfs(char[][] grid, int x, int y) {
    //如果超出边界，直接返回
    if (!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)) return;

    // 如果这个格子不是岛屿，直接返回
    if (grid[x][y] != '1') return; 

    grid[x][y] = '2'; //标记为已访问过
    dfs(grid, x + 1, y);
    dfs(grid, x - 1, y);
    dfs(grid, x, y + 1);
    dfs(grid, x, y - 1);
}

例题一：岛屿的数量

public int numIslands(char[][] grid) {
    int cnt = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                cnt++;
                dfs(grid, i, j);
            }
        }
    }
    return cnt;
}

public void dfs(char[][] grid, int x, int y) {
    //如果超出边界，直接返回
    if (!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)) return;

    // 如果这个格子不是岛屿，直接返回
    if (grid[x][y] != '1') return; 

    grid[x][y] = '2'; //标记为已访问过
    dfs(grid, x + 1, y);
    dfs(grid, x - 1, y);
    dfs(grid, x, y + 1);
    dfs(grid, x, y - 1);
}

例题二：岛屿的最大面积

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

public int area(int[][] grid, int x, int y) {
    //如果超出边界，直接返回
    if (!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)) return 0;

    // 如果这个格子不是岛屿，直接返回
    if (grid[x][y] != 1) return 0;

    grid[x][y] = 2; //标记为已访问过
    return 1 + area(grid, x + 1, y)
            + area(grid, x - 1, y)
            + area(grid, x, y + 1)
            + area(grid, x, y - 1);
}

例题三：填海造陆问题

public int largestIsland(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int flag = 2; //旗子从2开始，避免和岛屿1冲突
    HashMap<Integer, Integer> flagAndArea = new HashMap<>(); //存放岛屿的序号对应的面积
    int ans = 1;

    //遍历岛屿，计算出面积
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                int area = area(grid, i, j, flag);
                flagAndArea.put(flag, area);
                ans = Math.max(ans, area);
                flag++;
            }
        }
    }

    //遍历海洋
    int[][] d = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                HashSet<Integer> flags = new HashSet<>();
                for (int k = 0; k < 4; k++) {
                    int x = i + d[k][0];
                    int y = j + d[k][1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        if (grid[x][y] != 0) //若四周不是海洋
                            flags.add(grid[x][y]);
                    }
                }

                if (flags.size() >= 1) {
                    int sumArea = 1;
                    for (Integer f : flags) sumArea += flagAndArea.get(f);
                    ans = Math.max(ans, sumArea);
                }
            }
        }
    }

    return ans;
}

public int area(int[][] grid, int x, int y, int flag) {
    //如果超出边界，直接返回
    if (!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)) return 0;

    // 如果这个格子不是岛屿，直接返回
    if (grid[x][y] != 1) return 0;

    grid[x][y] = flag; //标记为已访问过
    return 1 + area(grid, x + 1, y, flag)
            + area(grid, x - 1, y, flag)
            + area(grid, x, y + 1, flag)
            + area(grid, x, y - 1, flag);
}

例题四：岛屿的周长

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

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                return length(grid, i, j);
            }
        }
    }
    return 0;
}

public int length(int[][] grid, int x, int y) {
    //如果超出边界，直接返回
    if (!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)) return 0;

    // 如果这个格子不是岛屿，直接返回
    if (grid[x][y] != 1) return 0;

    grid[x][y] = 2; //标记为已访问过

    //判断该格子四周有几个已标记
    int cnt = 0;
    int[][] d = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    for (int k = 0; k < 4; k++) {
        int i = x + d[k][0];
        int j = y + d[k][1];
        if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length) {
            if (grid[i][j] == 2) cnt++;
        }
    }

    int length = 0; //length为添加该格子后周长的损失
    if (cnt == 0) length = 4;
    else if (cnt == 1) length = 2;
    else if (cnt == 2) length = 0;
    else if (cnt == 3) length = -2;
    else if (cnt == 4) length = -4;

    return length + length(grid, x + 1, y)
            + length(grid, x - 1, y)
            + length(grid, x, y + 1)
            + length(grid, x, y - 1);
}

参考https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/

hhhhh