思路y总已经讲的很清楚了,但是我对如何实现边界检查还是不懂
仔细查看代码......
bfs函数的目的是为了找出从给定点出发所能到达的所有陆地像素,并判断这片区域是否会被完全淹没。如果一个岛屿的所有陆地像素都与海洋相邻,那么这个岛屿将会被完全淹没。
下面是bfs
函数的详细解析:
- 初始化队列:函数首先创建了一个队列que,用来存放接下来要探索的陆地像素点。
- 标记起点:将起始点(x, y)添加到队列中,并标记为已访问。
- 遍历队列:函数进入一个循环,不断遍历队列中的元素,直到队列为空。队列中的每个元素代表一个陆地像素点。
- 探索相邻点:对于队列中的每个点,函数会检查它的四个方向(上下左右)。如果相邻点是陆地且未被访问过,就将其加入队列并标记为已访问。
- 边界检测:如果任何一个陆地像素点的相邻点是海洋,那么这个点就处于边界上。函数通过is_bound变量来跟踪这个信息。
- 返回值:最后,函数检查这片区域的陆地像素总数是否等于边界上的陆地像素数。如果相等,意味着这个岛屿的所有陆地像素都与海洋相邻,因此将被完全淹没,函数返回true。
具体的边界检查:
这段代码遍历了当前陆地像素点temp
的四个方向。对于每个方向,我们计算相邻像素的坐标(a, b)
。接下来,我们进行以下检查:
- 越界检查:如果
(a, b)
超出了地图的范围,我们就跳过这个方向的检查,因为它不是有效的陆地或海洋像素。 - 已访问检查:如果相邻像素已经被访问过(意味着它已经被加入到队列中),我们也跳过这个方向的检查,以避免重复处理。
- 海洋检查:如果相邻像素是海洋
(g[a][b] == '.')
,那么我们知道当前的陆地像素点temp
至少有一个边界是与海洋相邻的,于是将is_bound
标记为true
。
如果is_bound
在检查完所有四个方向后仍为true
,这意味着当前的陆地像素点至少有一个方向与海洋相邻,即这个像素点处于岛屿的边缘。在遍历整个岛屿的所有陆地像素后,如果岛屿上每一个陆地像素都至少有一个方向与海洋相邻(即total == bound
),则这个岛屿会被完全淹没。
import java.util.*;
public class Main {
static final int N = 1010; // 定义最大的地图尺寸
static int n; // 实际使用的地图尺寸
static char[][] g = new char[N][N]; // 存储地图数据
static boolean[][] st = new boolean[N][N]; // 标记某个位置是否被访问过
static int[] dx = new int[]{-1, 0, 1, 0}; // 用于控制上下移动
static int[] dy = new int[]{0, 1, 0, -1}; // 用于控制左右移动
public static void main(String[] args) {
Scanner sca = new Scanner(System.in);
n = sca.nextInt();
for (int i = 0; i < n ; i++ ) {
char[] charArray = sca.next().toCharArray();
for (int j = 0; j < n; j++ ) {
g[i][j] = charArray[j]; // 读入地图数据
}
}
int cnt = 0; // 用于计数将被完全淹没的岛屿数量
for (int i = 0; i < n; i++ ) {
for (int j = 0; j < n; j++ ) {
if (!st[i][j] && g[i][j] == '#') { // 如果该点是陆地并且未被访问过
if (bfs(i, j)) { // 如果该岛屿将被完全淹没
cnt++; // 增加计数
}
}
}
}
System.out.println(cnt); // 输出将被完全淹没的岛屿数量
}
public static boolean bfs(int x, int y) {
Queue<PII> que = new LinkedList<>(); // 创建队列
que.add(new PII(x, y)); // 将起点加入队列
st[x][y] = true; // 标记起点
int total = 0; // 用于统计该岛屿的陆地像素总数
int bound = 0; // 用于统计处于边界的陆地像素数
while (!que.isEmpty()) {
PII temp = que.poll(); // 取出队列头部的元素
total++;
boolean is_bound = false; // 标记该像素是否处于边界
for (int i = 0; i < 4; i++ ) {
int a = temp.x + dx[i]; // 计算相邻像素的横坐标
int b = temp.y + dy[i]; // 计算相邻像素的纵坐标
if (a < 0 || a >= n || b < 0 || b >= n) continue; // 越界检查
if (st[a][b]) continue; // 已访问检查
if (g[a][b] == '.') { // 如果相邻像素是海洋
is_bound = true; // 当前陆地像素处于边界
continue;
}
que.add(new PII(a, b)); // 将未访问的陆地像素加入队列
st[a][b] = true; // 标记为已访问
}
if (is_bound) bound++; // 如果当前像素处于边界,则增加边界计数
}
return total == bound; // 如果所有陆地像素都处于边界,则岛屿将被完全淹没
}
}
class PII {
public int x;
public int y;
public PII(int x, int y) {
this.x = x;
this.y = y;
}
}