问题描述

讯享网

答案提交

解题思路

这道题需要用两个bfs解决，一个bfs用来搜索有多少个岛屿（包括子岛屿）。

另一个bfs用来排除子岛屿，方法是从每个岛屿起始点的上方一个海水点开始遍历，注意有8个方向！！！从第二个样例的第三个岛可以看出来。

一些需要注意的点：1.输入是一行连在一起的，所以要用字符串读入后拆分。

                                 2.边界是0~m-1和0~n-1，不是0~m和0~n。

详细部分见代码注释！！！

AC代码

import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; //Pos的作用类似c++的结构体，存储点的坐标 class Pos { int x, y; public Pos(int x, int y) { this.x = x; this.y = y; } } public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); // 读取测试用例数量 int t = scan.nextInt(); // 遍历每个测试用例 while (t-- > 0) { // 读取岛屿的行数和列数 int m = scan.nextInt(); int n = scan.nextInt(); // 初始化岛屿数量 int ans = 0; // 岛屿矩阵和访问标记矩阵 int[][] island = new int[m][n]; boolean[][] visited = new boolean[m][n]; // BFS 队列 Queue<Pos> queue = new LinkedList<>(); // 存储每个岛屿的第一个点的位置 ArrayList<Pos> firstPos = new ArrayList<Pos>(); // 方向数组：上、右、下、左 int[] dx = {-1, 0, 1, 0}; int[] dy = {0, 1, 0, -1}; // 读取岛屿矩阵 注意题目输入的数字是连着的，所以要用字符串读入后拆分 for (int i = 0; i < m; i++) { char[] str = scan.next().toCharArray(); for (int j = 0; j < n; j++) { island[i][j] = str[j] - '0'; } } // 遍历岛屿矩阵 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 如果当前位置未访问且为岛屿 if (visited[i][j] == false && island[i][j] == 1) { // 岛屿数量加一 ans++; // 存储第一个点的位置 firstPos.add(new Pos(i, j)); // 将第一个点入队列，开始 BFS queue.offer(new Pos(i, j)); visited[i][j] = true; while (!queue.isEmpty()) { Pos pos = queue.poll(); // 遍历上、右、下、左四个方向 for (int k = 0; k < 4; k++) { int x = pos.x + dx[k]; int y = pos.y + dy[k]; // 判断新位置是否在合法范围0~n-1和0~m-1内，并且为未访问的岛屿点 if (x >= 0 && x < m && y >= 0 && y < n && island[x][y] == 1 && !visited[x][y]) { visited[x][y] = true; queue.offer(new Pos(x, y)); } } } } } } // 接下来从每个岛的第一个点的上方一个点（由遍历方式易得这个点一定是海水）开始遍历海水 // 只要能遍历到边界就说明不是子岛屿 // 方向数组：上、右上、右、右下、下、左下、左、左上 int[] dxSea = {-1, -1, 0, 1, 1, 1, 0, -1}; int[] dySea = {0, 1, 1, 1, 0, -1, -1, -1}; // 遍历存储的每个岛屿的第一个点的位置 outer: for (Pos pos : firstPos) { boolean[][] visitedSea = new boolean[m][n]; // 如果该岛屿的第一个点在边界上，直接跳过 if (pos.x == 0 || pos.x == m - 1 || pos.y == 0 || pos.y == n - 1) { continue; } queue.clear(); queue.offer(new Pos(pos.x - 1, pos.y)); while (!queue.isEmpty()) { Pos posNow = queue.poll(); // 如果海的点到达边界，说明不是子岛屿，跳到外循环 if (posNow.x == 0 || posNow.x == m - 1 || posNow.y == 0 || posNow.y == n - 1) { continue outer; } // 遍历左上、上、右上、右、右下、下、左下、左八个方向 for (int k = 0; k < 8; k++) { int x = posNow.x + dxSea[k]; int y = posNow.y + dySea[k]; // 判断新位置是否在合法范围内，并且为未访问的海点 if (x >= 0 && x < m && y >= 0 && y < n && island[x][y] == 0 && !visitedSea[x][y]) { visitedSea[x][y] = true; queue.offer(new Pos(x, y)); } } } // 遍历完整个岛都没有接触到边界，说明是子岛屿，不合题意 // 岛屿数量减一 ans--; } // 输出结果 System.out.println(ans); } // 关闭输入流 scan.close(); } } 

相关知识 

带有标记的 continue 语句

在 Java 中，continue 语句通常用于跳过当前迭代的剩余部分，直接进入下一次迭代。有时候，可能需要在嵌套循环中使用 continue 语句，这时可以使用标记（label）来标识外层循环，并在 continue 语句中指定标记，以明确要跳过哪个循环。

示例：

讯享网public class ContinueWithLabel { public static void main(String[] args) { outerLoop: // 外层循环标记 for (int i = 0; i < 3; i++) { innerLoop: // 内层循环标记 for (int j = 0; j < 3; j++) { if (i == 1 && j == 1) { // 当 i 等于 1 且 j 等于 1 时，跳过外层循环的当前迭代 continue outerLoop; } System.out.println("i: " + i + ", j: " + j); } } } } 

在这个例子中，outerLoop 是外层循环的标记，innerLoop 是内层循环的标记。当 i 等于 1 且 j 等于 1 时，continue outerLoop; 将跳过外层循环的当前迭代，直接进入下一次外层循环。

BFS代码举例分析

 参考：蓝桥杯第3513题——岛屿个数

（by 归忆）