算法训练营day53 | {101.孤岛的总面积, 102.沉没孤岛, 103.水流问题, 104.建造最大岛屿}

第11章图论-part03，继续用深搜/广搜解决岛屿问题，优化思路很妙。

101. 孤岛的总面积

1.1 解题小结

题解的做法比我更好，它把和矩阵边缘有接触的陆地全部置为0，重新遍历一遍grid矩阵，剩余1的个数就是孤岛的总面积。
本题不需要定义visited数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.*;

public class Main {

    static int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void main(String[] args) {
        int res = 0;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] grid = new int[n][m];
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            bfs(grid, i, 0);
            bfs(grid, i, m - 1);
        }

        for (int j = 0; j < m; j++) {
            bfs(grid, 0, j);
            bfs(grid, n - 1, j);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) res++;
            }
        }
        System.out.println(res);
    }

    private static void bfs(int[][] grid, int x, int y) {
        Deque<int[]> queue = new ArrayDeque<>();
        if (grid[x][y] == 0) return;
        queue.offerLast(new int[]{x, y});
        grid[x][y] = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.pollFirst();
            for (int i = 0; i < 4; i++) {
                int nextX = cur[0] + dir[i][0];
                int nextY = cur[1] + dir[i][1];
                if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
                if (grid[nextX][nextY] == 1) {
                    queue.offerLast(new int[]{nextX, nextY});
                    grid[nextX][nextY] = 0;
                }
            }
        }
    }
}

102. 沉没孤岛

2.1 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.*;

public class Main {

    static int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] grid = new int[n][m];
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            bfs(grid, i, 0);
            bfs(grid, i, m - 1);
        }

        for (int j = 0; j < m; j++) {
            bfs(grid, 0, j);
            bfs(grid, n - 1, j);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = grid[i][j] > 0 ? grid[i][j] - 1 : 0;
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static void bfs(int[][] grid, int x, int y) {
        Deque<int[]> queue = new ArrayDeque<>();
        if (grid[x][y] == 0) return;
        queue.offerLast(new int[]{x, y});
        grid[x][y] = 2;
        while (!queue.isEmpty()) {
            int[] cur = queue.pollFirst();
            for (int i = 0; i < 4; i++) {
                int nextX = cur[0] + dir[i][0];
                int nextY = cur[1] + dir[i][1];
                if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
                if (grid[nextX][nextY] == 1) {
                    queue.offerLast(new int[]{nextX, nextY});
                    grid[nextX][nextY] = 2;
                }
            }
        }
    }
}

103. 水流问题

3.1 解题分析

提示信息
图中的蓝色方块上的雨水既能流向第一组边界，也能流向第二组边界。所以最终答案为所有蓝色方块的坐标。

3.2 解题小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;

public class Main {

    static int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] grid = new int[n][m];
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        boolean[][] firstBorder = new boolean[n][m];
        boolean[][] secondBorder = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            dfs(grid, firstBorder, i, 0);
            dfs(grid, secondBorder, i, m - 1);
        }

        for (int j = 0; j < m; j++) {
            dfs(grid, firstBorder, 0, j);
            dfs(grid, secondBorder, n - 1, j);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (firstBorder[i][j] && secondBorder[i][j]) {
                    System.out.println(i + " " + j);
                }
            }
        }
    }

    private static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        if (visited[x][y]) return;
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
            if (grid[nextX][nextY] >= grid[x][y]) {
                dfs(grid, visited, nextX, nextY);
            }
        }
    }
}

104. 建造最大岛屿

4.1 解题分析

本题的一个暴力想法，应该是遍历地图尝试 将每一个 0 改成1，然后去搜索地图中的最大的岛屿面积。但这个时间复杂度同样是O(n^4)级别的，优化思路是什么？

只要用一次深搜把每个岛屿的面积记录下来就好。

第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积

第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。

4.2 解题小结

注意在统计相邻的陆地面积时，用过一次的陆地要标记一下，避免重复统计面积。这里我用的是Set集合记录对应的mark。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.*;

public class Main {

    static int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static int cnt = 0;

    public static void main(String[] args) {
        int res = 0;
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] grid = new int[n][m];
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                grid[i][j] = scanner.nextInt();
            }
        }

        Map<Integer, Integer> infos = new HashMap<>();
        int mark = 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    cnt = 1;
                    grid[i][j] = mark;
                    dfs(grid, mark, i, j);
                    infos.put(mark, cnt);
                    res = Math.max(res, cnt);
                    mark++;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] != 0) continue;
                Set<Integer> used = new HashSet<>();
                int tmp = 1;
                for (int k = 0; k < 4; k++) {
                    int nearX = i + dir[k][0];
                    int nearY = j + dir[k][1];
                    if (nearX < 0 || nearX >= n || nearY < 0 || nearY >= m || used.contains(grid[nearX][nearY])) continue;
                    tmp += infos.getOrDefault(grid[nearX][nearY], 0);
                    used.add(grid[nearX][nearY]);
                }
                res = Math.max(res, tmp);
            }
        }
        System.out.println(res);
    }

    private static void dfs(int[][] grid, int mark, int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length) continue;
            if (grid[nextX][nextY] == 1) {
                cnt++;
                grid[nextX][nextY] = mark;
                dfs(grid, mark, nextX, nextY);
            }
        }
    }
}

4. 今日收获

  • 学习时长：4小时
Leetcode > 图论
#Java #代码随想录
算法训练营day53 | {101.孤岛的总面积, 102.沉没孤岛, 103.水流问题, 104.建造最大岛屿}
http://paopaotangzu.xyz/cn/day53_leetcode/
作者
PROTON TANG
发布于
2026年2月9日
许可协议