蓝桥杯错题本

发表于 2025-03-19

3513 岛屿个数

#外岛数量 #bfs

杰克船长算法

杰克船长在公海上游荡，每发现一处岛屿，他就会绕着岛走一圈，并把这个岛标记到地图上。

这个问题的解决方法就在这里：我们一定要有一片完全连通的公海，只有在公海上遇到岛屿，才标记岛屿数量；绝不踏入内海。

可是测试用例是这样的：

这个测试用例，只有(0, 0)是公海，怎么办呢？
我们用一圈公海把测试用例包围起来：

private static void processInput(Scanner sc) {
    M = sc.nextInt();
    N = sc.nextInt();
    sc.nextLine();
    map = new int[M + 2][N + 2]; // 注意+2，多一圈'0'表示公海
    visitedSea = new boolean[M + 2][N + 2];
    visitedIsland = new boolean[M + 2][N + 2];
    cnt = 0;
    for (int x = 1; x <= M; x += 1) {
        String line = sc.nextLine();
        for (int y = 1; y <= N; y += 1) {
            map[x][y] = line.charAt(y - 1) - '0';
        }
    }
}

接着就是对最外面一圈公海进行bfs遍历，只有在公海遇到岛屿才上岛：

private static void bfsSea(int x, int y) {
    Queue<Point> queue = new LinkedList<>();
    queue.add(new Point(x, y));
    visitedSea[x][y] = true;

    while (!queue.isEmpty()) {
        Point point = queue.poll();
        for (int d = 0; d < 8; d += 1) { // 8个方向！
            int nx = point.x + dx[d];
            int ny = point.y + dy[d];
            if (!isOutBound(nx, ny)) {
                if (!visitedSea[nx][ny] && map[nx][ny] == 0) {
                    visitedSea[nx][ny] = true;
                    queue.add(new Point(nx, ny));
                } else if (!visitedIsland[nx][ny] && map[nx][ny] == 1) {
                    cnt++;
                    bfsIsland(nx, ny);
                }
            }
        }
    }
}

注意测试用例的边界情况

上面这个测试用例告诉我们：公海可以朝8个方向通行。而岛屿我们只朝4面通行

private static void bfsIsland(int x, int y) {
    Queue<Point> queue = new LinkedList<>();
    queue.add(new Point(x, y));
    visitedIsland[x][y] = true;

    while (!queue.isEmpty()) {
        Point point = queue.poll();
        for (int d = 0; d < 4; d += 1) { // 4个方向
            int nx = point.x + dx[d];
            int ny = point.y + dy[d];
            if (!isOutBound(nx, ny) && !visitedIsland[nx][ny] && map[nx][ny] == 1) {
                visitedIsland[nx][ny] = true;
                queue.add(new Point(nx, ny));
            }
        }
    }
}

完整调用如下：
如果WA，可以把访问点全部打印出来，看看是不是代码有漏洞导致没遍历完

static int[][] map;
static boolean[][] visitedSea;
static boolean[][] visitedIsland;
static int M, N;
static int cnt;

public static void solution() {
    List<Integer> ans = new ArrayList<>();
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for (int i = 0; i < T; i += 1) {
        processInput(sc);
        // printMap();

        // 外面一圈都是公海，所以从(0, 0)开始就可以遍历整个公海
        bfsSea(0, 0); 
        ans.add(cnt);
        // printVisited();
    }
    sc.close();
    for (int answer : ans) {
        System.out.println(answer);
    }
}

private static class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

// 上、下、左、右、左上、左下、右上、右下
static int[] dx = { -1, 1, 0, 0, -1, 1, -1, 1 };
static int[] dy = { 0, 0, -1, 1, -1, -1, 1, 1 };