算法训练营day52 | {99.岛屿数量(深搜), 99.岛屿数量(广搜), 100.岛屿的最大面积}

第11章图论-part02，正式用深搜和广搜解题，今天比较简单。

99. 岛屿数量(深搜)

1.1 解题分析

本题思路是，按行遍历grid矩阵，遇到一个没有遍历过的节点陆地，计数器就加1，然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点或海洋节点时，直接跳过。

那么如何把节点陆地所能遍历到的陆地都标记上呢？就要用到搜索算法，如DFS、BFS或并查集。

1.2 解题小结

  • 深搜–版本一，调用dfs一定是合法的，故没有终止条件。
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
import java.util.Scanner;

public class Main {

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

    public static void main(String[] args) {
        int cnt = 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++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    cnt++;
                    visited[i][j] = true;
                    dfs(grid, visited, i, j);
                }
            }
        }
        System.out.println(cnt);
    }

    private static void dfs(int[][] grid, boolean[][] visited, 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 && !visited[nextX][nextY]) {
                visited[nextX][nextY] = true;
                dfs(grid, visited, nextX, nextY);
            }
        }
    }
}
  • 深搜–版本二，压力给到终止条件，不管节点是否合法，上来就调用dfs，不合法则return。
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
import java.util.Scanner;

public class Main {

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

    public static void main(String[] args) {
        int cnt = 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++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    cnt++;
                    dfs(grid, visited, i, j);
                }
            }
        }
        System.out.println(cnt);
    }

    private static void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        if (grid[x][y] == 0 || 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;
            dfs(grid, visited, nextX, nextY);
        }
    }
}

注意这种dfs的写法，判断完合法性之后，进入节点后立即标记已访问过，避免其他递归路径可能再次进入这个节点，导致重复统计。

99.岛屿数量(广搜)

2.1 解题分析

思路还是一样，遍历到未访问过的陆地节点，要将其相邻陆地节点标记为访问过，这次借助广搜来实现。

注意，我们对代码中队列的定义，是队列中的节点就表示已经走过的节点。所以只要加入队列，立即标记该节点走过。而不是从队列中取出节点时再标记已访问过，后者会导致超时。

2.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
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 cnt = 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++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    cnt++;
                    bfs(grid, visited, i, j);
                }
            }
        }
        System.out.println(cnt);
    }

    private static void bfs(int[][] grid, boolean[][] visited, int x, int y) {
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offerLast(new int[]{x, y});
        visited[x][y] = true;
        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 && !visited[nextX][nextY]) {
                    queue.offerLast(new int[]{nextX, nextY});
                    visited[nextX][nextY] = true;
                }
            }
        }
    }
}

100. 岛屿的最大面积

3.1 解题小结

  • 拿广搜的代码稍微改了下，cnt也可以定义为全局成员变量。
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
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++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    res = Math.max(res, bfs(grid, visited, i, j));
                }
            }
        }
        System.out.println(res);
    }

    private static int bfs(int[][] grid, boolean[][] visited, int x, int y) {
        int cnt = 1;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offerLast(new int[]{x, y});
        visited[x][y] = true;
        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 && !visited[nextX][nextY]) {
                    queue.offerLast(new int[]{nextX, nextY});
                    visited[nextX][nextY] = true;
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

4. 今日收获

  • 岛屿问题，不限制搜索的遍历方式。
  • 学习时长：2.5小时
Leetcode > 图论
#Java #代码随想录
算法训练营day52 | {99.岛屿数量(深搜), 99.岛屿数量(广搜), 100.岛屿的最大面积}
http://paopaotangzu.xyz/cn/day52_leetcode/
作者
PROTON TANG
发布于
2026年2月9日
许可协议