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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
/**
* 主方法：处理吴铭市地图数据并统计被完全淹没的区域数量
*
* 业务逻辑：
* 1. 读取 N*N 的城市地图。
* 2. 通过遍历寻找每一个独立的“空地区域”（由 '#' 组成的四连通块）。
* 3. 对每个区域进行洪水上涨模拟判定。
*
* @param args 命令行参数
* @throws IOException IO异常处理
*/
public static void main(String[] args) throws IOException {
// 使用高效流读取地图数据与输出结果
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
// 读取地图尺寸 N
int N = Integer.parseInt(br.readLine().trim());
// grid: 地图矩阵，'.' 为已淹没，'#' 为空地
char[][] grid = new char[N][N];
// visit: 标记当前空地是否已被抗灾委员会统计过
boolean[][] visit = new boolean[N][N];
// 加载吴铭市当前受灾地图
for (int i = 0; i < N; i++) {
grid[i] = br.readLine().trim().toCharArray();
}
// ans: 记录洪水上涨一天后，完全消失的空地区域总数
int ans = 0;
// 逐格扫描地图
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 发现一块新的且未统计过的空地区域
if (grid[i][j] == '#' && !visit[i][j]) {
/**
* 执行 BFS 模拟：
* 若该区域内所有格子在明天都会被淹没（即 bfs 返回 false），
* 则该区域属于“完全淹没区域”，计数加一。
*/
if (!bfs(grid, N, i, j, visit)) {
ans++;
}
}
}
}
// 输出统计结果并释放资源
out.println(ans);
out.flush();
out.close();
br.close();
}
/**
* 使用广度优先搜索 (BFS) 判定一个空地区域在洪水上涨后是否能“存活”
*
* 判定核心：
* 一个区域能存活，当且仅当该区域内【至少有一个】格子是安全的。
* 安全格子的定义：其上下左右四个相邻方向全部都是空地 '#'，洪水无法直接上涨淹没它。
*
* @param grid 城市地图矩阵
* @param N 地图尺寸
* @param i 区域起始点行坐标
* @param j 区域起始点列坐标
* @param visit 访问标记数组
* @return 如果该区域上涨后仍有残留（不完全消失）返回 true，否则返回 false
*/
private static boolean bfs(char[][] grid, int N, int i, int j, boolean[][] visit) {
Queue<int[]> queue = new LinkedList<>();
// 将当前区域的起点加入队列并标记
queue.add(new int[]{i, j});
visit[i][j] = true;
// areaSurvived: 标识整个区域是否能存活（只要有一个格子不被淹，即为 true）
boolean areaSurvived = false;
// 四联通方向向量
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0];
int y = cur[1];
// flag: 检查当前格子 (x, y) 是否为“避风港”
// 默认假设它是安全的（四周无洪水 '.'）
boolean flag = true;
// 扫描当前格子的四周
for (int k = 0; k < 4; k++) {
int nextX = x + dx[k];
int nextY = y + dy[k];
// 如果邻居越界或者是洪水 '.'，则当前格子明早会被淹没
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N || grid[nextX][nextY] == '.') {
flag = false;
break;
}
}
// 如果发现当前格子四周都是空地，它将保证该区域不被完全淹没
if (flag) {
areaSurvived = true;
}
// 继续探索该区域的其他空地格子
for (int k = 0; k < 4; k++) {
int nextX = x + dx[k];
int nextY = y + dy[k];
// 确保在地图范围内，且是同一区域的未访问空地
if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && grid[nextX][nextY] == '#' && !visit[nextX][nextY]) {
visit[nextX][nextY] = true;
queue.add(new int[]{nextX, nextY});
}
}
}
// 返回该区域是否完全消失
return areaSurvived;
}
|
