2025 A卷 100分 题型
本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；
并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；
本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》
华为OD机试真题《战场索敌》：
文章快捷目录
题目描述及说明
Java
python
JavaScript
C
GO
更多内容
题目名称：战场索敌
知识点：深度优先搜索（DFS）、广度优先搜索（BFS）、逻辑处理
时间限制：1秒
空间限制：256MB
限定语言：不限
题目描述
有一个大小为N×M的战场地图，被墙壁 # 分隔成不同的区域。上下左右四个方向相邻的空地 . 属于同一区域，只有空地上可能存在敌人 E。要求统计地图中敌人数小于K的区域数量。
输入描述
- 第一行输入三个整数N、M、K，分别表示地图的行数、列数和目标敌人数阈值（N, M ≤ 100）。
- 接下来输入一个N×M的字符数组，表示战场地图，包含字符
#（墙壁）、.（空地）、E（敌人）。
输出描述
- 输出一个整数，表示敌人数小于K的区域数量。
示例
输入：
3 5 2
..#EE
E.#E.
###..
输出：
1
说明
- 地图被墙壁分为两个区域：左侧区域有1个敌人，右侧区域有3个敌人，仅左侧区域满足条件。
输入约束
- 输入保证每个区域的敌人数量为非负整数。
- 任意两个敌人位置不重叠。
Java
问题分析
题目要求统计战场地图中被墙壁分隔的各个区域中，敌人数小于给定阈值的区域数量。每个区域由上下左右相邻的空地（包括敌人所在位置）组成，我们需要遍历每个区域并统计其中的敌人数。
解题思路
- 输入处理：读取地图的行数、列数和阈值K，然后读取地图数据。
- 遍历地图：使用双重循环遍历每个地图位置。
- 区域标记与统计：对于每个未被访问且非墙壁的位置，使用广度优先搜索（BFS）遍历整个区域，统计区域内的敌人数量。
- 判断条件：如果当前区域的敌人数小于K，则计入结果。
- 输出结果：统计符合条件的区域数量并输出。
代码实现
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入参数 N, M, K
int N = scanner.nextInt();
int M = scanner.nextInt();
int K = scanner.nextInt();
scanner.nextLine(); // 跳过换行符
// 读取战场地图数据
char[][] grid = new char[N][M];
for (int i = 0; i < N; i++) {
String line = scanner.nextLine().trim();
for (int j = 0; j < M; j++) {
grid[i][j] = line.charAt(j);
}
}
// 标记数组，记录每个位置是否被访问过
boolean[][] visited = new boolean[N][M];
int count = 0; // 符合条件的区域数量
// 方向数组，用于BFS遍历四个方向
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
// 遍历地图中的每个位置
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// 如果当前位置是墙壁或已被访问，跳过
if (grid[i][j] == '#' || visited[i][j]) {
continue;
}
// BFS初始化
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
visited[i][j] = true;
int cnt = 0; // 当前区域的敌人数
// 如果当前起始位置是敌人，计数加1
if (grid[i][j] == 'E') {
cnt++;
}
// BFS遍历
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0];
int y = curr[1];
// 遍历四个方向
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
// 检查新位置是否合法且未被访问，且不是墙壁
if (nx >= 0 && nx < N && ny >= 0 && ny < M
&& !visited[nx][ny] && grid[nx][ny] != '#') {
visited[nx][ny] = true;
// 如果是敌人，计数加1
if (grid[nx][ny] == 'E') {
cnt++;
}
queue.offer(new int[]{nx, ny});
}
}
}
// 判断当前区域的敌人数是否小于K
if (cnt < K) {
count++;
}
}
}
// 输出结果
System.out.println(count);
}
}
代码详细解析
- 输入处理：通过
Scanner读取输入参数和地图数据，存储到二维数组grid中。 - 初始化标记数组：
visited数组用于记录每个位置是否已被访问，避免重复处理。 - 方向数组：
dx和dy数组表示上下左右四个方向的坐标变化。 - 遍历地图：双重循环遍历每个位置，跳过已访问或为墙壁的位置。
- BFS初始化：发现未被访问的非墙壁位置时，初始化队列，标记起始位置为已访问。
- 敌人数统计：在BFS遍历过程中，每当访问到一个新位置时，检查是否为敌人并计数。
- 方向遍历：对每个位置的四个方向进行处理，确保新位置合法且未被访问。
- 条件判断：当前区域遍历完成后，判断敌人数是否小于K，符合条件则计数。
- 输出结果：统计所有符合条件的区域数量并输出。
示例测试
示例1：
输入：
3 5 2
..#EE
E.#E.
###..
输出：
1
说明：左侧区域有1个敌人，右侧区域有3个敌人，仅左侧满足条件。
示例2：
输入：
2 2 1
.E
E.
输出：
0
说明：所有位置属于同一区域，敌人数为2，不小于1。
示例3：
输入：
1 5 3
E.E.E
输出：
1
说明：所有位置连通，敌人数为3，等于阈值3，不满足条件。但若K=4，则输出1。
综合分析
本方案采用BFS遍历每个区域，确保每个位置仅被访问一次，时间复杂度为O(N*M)，适用于最大规模为100x100的地图。BFS相比DFS更适合处理可能的深层次递归问题，避免栈溢出。代码通过标记数组和队列高效管理区域遍历，敌人数统计在访问时立即进行，确保正确性。该方法在时间复杂度和空间复杂度上均为最优，是解决此类连通区域问题的经典方案。
python
问题分析
我们需要统计战场地图中被墙壁分隔的各个区域中，敌人数小于给定阈值 K 的区域数量。每个区域由上下左右相邻的空地（包括敌人所在位置）组成，需遍历每个区域并统计其中的敌人数。
解题思路
- 输入处理：读取地图的行数
N、列数M和阈值K，然后读取地图数据。 - 遍历地图：用双重循环遍历每个位置。
- 区域标记与统计：对每个未被访问且非墙壁的位置，使用 广度优先搜索（BFS） 遍历整个区域，统计敌人数。
- 判断条件：若当前区域敌人数
< K，则计入结果。 - 输出结果：统计并输出符合条件的区域数量。
代码实现
from collections import deque
def main():
# 读取输入参数 N, M, K
N, M, K = map(int, input().split())
# 读取战场地图数据（处理可能的空格）
grid = []
for _ in range(N):
line = input().strip() # 去掉首尾空格或换行符
grid.append(list(line))
# 标记数组，记录每个位置是否被访问过
visited = [[False for _ in range(M)] for _ in range(N)]
count = 0 # 符合条件的区域数量
# 方向数组，表示上下左右四个方向的坐标变化
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 遍历地图中的每个位置
for i in range(N):
for j in range(M):
# 跳过已访问或墙壁的位置
if grid[i][j] == '#' or visited[i][j]:
continue
# BFS初始化：队列和当前区域的敌人数
queue = deque()
queue.append((i, j))
visited[i][j] = True
enemy_count = 0
# 如果起始位置是敌人，计数+1
if grid[i][j] == 'E':
enemy_count += 1
# 开始BFS遍历
while queue:
x, y = queue.popleft()
# 遍历四个方向
for dx, dy in directions:
nx, ny = x + dx, y + dy
# 检查新位置是否合法
if 0 <= nx < N and 0 <= ny < M:
# 跳过已访问或墙壁
if not visited[nx][ny] and grid[nx][ny] != '#':
visited[nx][ny] = True
# 如果是敌人，计数+1
if grid[nx][ny] == 'E':
enemy_count += 1
queue.append((nx, ny))
# 判断当前区域的敌人数是否小于K
if enemy_count < K:
count += 1
# 输出结果
print(count)
if __name__ == "__main__":
main()
代码详细解析
输入处理：
N, M, K = map(int, input().split())：读取第一行的三个整数。- 循环读取
N行地图数据，并存储到二维列表grid中。
标记数组：
visited是一个N×M的布尔数组，初始化为全False，表示每个位置是否被访问过。
方向数组：
directions定义四个移动方向（上、下、左、右），用于遍历相邻位置。
双重循环遍历地图：
- 外层循环遍历行
i，内层循环遍历列j。 - 如果当前位置是墙壁
#或已访问过，则跳过。
- 外层循环遍历行
BFS初始化：
- 使用
deque作为队列，起始位置(i, j)入队，并标记为已访问。 enemy_count统计当前区域的敌人数。
- 使用
BFS遍历：
- 从队列中取出一个位置
(x, y)。 - 遍历四个方向，计算新位置
(nx, ny)。 - 检查新位置是否合法（不越界、未被访问且不是墙壁）。
- 如果是敌人
E，则敌人数+1，并将新位置入队。
- 从队列中取出一个位置
判断条件：
- 遍历完一个区域后，若
enemy_count < K，则符合条件的区域数count +1。
- 遍历完一个区域后，若
示例测试
示例1：
输入：
3 5 2
..#EE
E.#E.
###..
输出：
1
说明：左侧区域有1个敌人，右侧区域有3个敌人，仅左侧满足条件。
示例2：
输入：
2 2 1
.E
E.
输出：
0
说明：所有位置属于同一区域，敌人数为2，不小于1。
示例3：
输入：
4 4 3
E.##
#.E#
##.#
.E.E
输出：
2
说明：地图被分为多个区域，其中两个区域的敌人数为1和2，均小于3。
综合分析
- 时间复杂度：
O(N×M)。每个位置最多被访问一次，BFS的队列操作是常数时间。 - 空间复杂度：
O(N×M)。存储地图和标记数组需要线性空间。 - 算法选择：
- BFS 更适合处理二维网格的连通区域问题，因为队列操作天然适合逐层扩展。
- 相比 DFS，BFS 不会因递归深度过大导致栈溢出，适合处理大规模数据。
- 实现优化：
- 使用
deque实现队列，保证入队和出队操作的时间复杂度为O(1)。 - 方向数组简化了代码逻辑，避免重复判断。
- 使用
- 适用场景：所有需要统计连通区域特性的问题（如岛屿数量、区域面积等）。
JavaScript
问题分析
我们需要统计战场地图中被墙壁分隔的各个区域中，敌人数小于给定阈值 K 的区域数量。每个区域由上下左右相邻的空地（包括敌人所在位置）组成，需遍历每个区域并统计其中的敌人数。
解题思路
- 输入处理：读取地图的行数
N、列数M和阈值K，并将地图存储为二维数组。 - 遍历地图：用双重循环遍历每个位置。
- 区域标记与统计：对每个未被访问且非墙壁的位置，使用 广度优先搜索（BFS） 遍历整个区域，统计敌人数。
- 判断条件：若当前区域敌人数
< K，则计入结果。 - 输出结果：统计并输出符合条件的区域数量。
代码实现
function main(input) {
const lines = input.trim().split('\n').map(line => line.trim());
const [N, M, K] = lines[0].split(' ').map(Number);
const grid = [];
for (let i = 1; i <= N; i++) {
grid.push(lines[i].split(''));
}
const visited = Array.from({ length: N }, () => Array(M).fill(false));
let count = 0;
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (grid[i][j] === '#' || visited[i][j]) continue;
const queue = [[i, j]];
visited[i][j] = true;
let enemyCount = grid[i][j] === 'E' ? 1 : 0;
while (queue.length > 0) {
const [x, y] = queue.shift();
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
if (!visited[nx][ny] && grid[nx][ny] !== '#') {
visited[nx][ny] = true;
if (grid[nx][ny] === 'E') enemyCount++;
queue.push([nx, ny]);
}
}
}
}
if (enemyCount < K) count++;
}
}
console.log(count);
}
// 测试输入示例
const input1 = `
3 5 2
..#EE
E.#E.
###..
`;
main(input1); // 输出: 1
const input2 = `
2 2 1
.E
E.
`;
main(input2); // 输出: 0
const input3 = `
4 4 3
E.##
#.E#
##.#
.E.E
`;
main(input3); // 输出: 2
代码详细解析
输入处理：
input.trim()去除首尾空格或换行符。split('\n')按行分割输入。lines[0]提取第一行，分割出N、M、K。- 后续行存入
grid二维数组，表示地图。
初始化标记数组：
visited是一个N×M的布尔数组，初始化为false，记录是否访问过某个位置。
方向数组：
directions定义上下左右四个方向，用于遍历相邻位置。
双重循环遍历地图：
- 外层循环遍历行
i，内层循环遍历列j。 - 若当前是墙壁
#或已访问，跳过。
- 外层循环遍历行
BFS初始化：
- 队列初始化为当前坐标
[i, j]，并标记为已访问。 enemyCount初始化为当前坐标是否为敌人（E）的计数值。
- 队列初始化为当前坐标
BFS遍历：
- 从队列中取出坐标
[x, y]。 - 遍历四个方向，计算新坐标
[nx, ny]。 - 检查新坐标是否合法（不越界、未被访问、不是墙壁）。
- 若合法，标记为已访问，并统计敌人数量。
- 从队列中取出坐标
判断条件：
- 遍历完一个区域后，若敌人数
< K，则结果count加一。
- 遍历完一个区域后，若敌人数
示例测试
示例1：
输入：
3 5 2
..#EE
E.#E.
###..
输出：
1
说明：左侧区域有1个敌人，右侧区域有3个敌人，仅左侧符合条件。
示例2：
输入：
2 2 1
.E
E.
输出：
0
说明：整个区域敌人总数为2，不小于1。
示例3：
输入：
4 4 3
E.##
#.E#
##.#
.E.E
输出：
2
说明：两个区域的敌人数分别为1和2，均符合条件。
综合分析
- 时间复杂度：
O(N×M)。每个位置最多被访问一次，BFS队列操作总体复杂度为线性。 - 空间复杂度：
O(N×M)。存储地图和标记数组需要线性空间。 - 算法选择：
- BFS 适合处理二维网格的连通区域问题，避免递归栈溢出。
- 队列操作通过
shift和push实现，虽然shift是O(n)，但数据规模较小，性能可接受。
- 实现优化：
- 立即标记已访问的格子，避免重复入队。
- 方向数组简化了代码逻辑，提高可读性。
- 适用场景：所有需要统计连通区域特性的问题（如岛屿数量、区域面积等）。
C++
问题分析
我们需要统计战场地图中被墙壁分隔的各个区域中，敌人数小于给定阈值 K 的区域数量。每个区域由上下左右相邻的空地（包括敌人所在位置）组成，需遍历每个区域并统计其中的敌人数。
解题思路
- 输入处理：读取地图的行数
N、列数M和阈值K，并将地图存储为二维数组。 - 遍历地图：用双重循环遍历每个位置。
- 区域标记与统计：对每个未被访问且非墙壁的位置，使用 广度优先搜索（BFS） 遍历整个区域，统计敌人数。
- 判断条件：若当前区域敌人数
< K，则计入结果。 - 输出结果：统计并输出符合条件的区域数量。
代码实现
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int N, M, K;
cin >> N >> M >> K;
// 读取地图数据
vector<string> grid(N);
for (int i = 0; i < N; ++i) {
cin >> grid[i];
}
// 标记数组，记录每个位置是否被访问过
vector<vector<bool>> visited(N, vector<bool>(M, false));
int count = 0; // 符合条件的区域数量
// 方向数组，表示上下左右四个方向的坐标变化
const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 遍历地图中的每个位置
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
// 跳过已访问或墙壁的位置
if (grid[i][j] == '#' || visited[i][j]) {
continue;
}
// BFS初始化：队列和当前区域的敌人数
queue<pair<int, int>> q;
q.emplace(i, j);
visited[i][j] = true;
int enemy_count = 0;
// 如果起始位置是敌人，计数+1
if (grid[i][j] == 'E') {
enemy_count++;
}
// 开始BFS遍历
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
// 遍历四个方向
for (const auto& d : dirs) {
int nx = x + d[0];
int ny = y + d[1];
// 检查新位置是否合法
if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
// 跳过已访问或墙壁
if (!visited[nx][ny] && grid[nx][ny] != '#') {
visited[nx][ny] = true;
// 如果是敌人，计数+1
if (grid[nx][ny] == 'E') {
enemy_count++;
}
q.emplace(nx, ny);
}
}
}
}
// 判断当前区域的敌人数是否小于K
if (enemy_count < K) {
count++;
}
}
}
// 输出结果
cout << count << endl;
return 0;
}
代码详细解析
输入处理：
cin >> N >> M >> K：读取第一行的三个整数。- 循环读取
N行地图数据，存储到vector<string> grid中。
标记数组：
visited是一个N×M的布尔数组，初始化为全false，表示每个位置是否被访问过。
方向数组：
dirs定义四个移动方向（上、下、左、右），用于遍历相邻位置。
双重循环遍历地图：
- 外层循环遍历行
i，内层循环遍历列j。 - 如果当前位置是墙壁
#或已访问过，则跳过。
- 外层循环遍历行
BFS初始化：
- 使用
queue<pair<int, int>>作为队列，起始位置(i, j)入队，并标记为已访问。 enemy_count统计当前区域的敌人数。
- 使用
BFS遍历：
- 从队列中取出一个位置
(x, y)。 - 遍历四个方向，计算新位置
(nx, ny)。 - 检查新位置是否合法（不越界、未被访问且不是墙壁）。
- 如果是敌人
E，则敌人数+1，并将新位置入队。
- 从队列中取出一个位置
判断条件：
- 遍历完一个区域后，若
enemy_count < K，则符合条件的区域数count +1。
- 遍历完一个区域后，若
示例测试
示例1：
输入：
3 5 2
..#EE
E.#E.
###..
输出：
1
说明：左侧区域有1个敌人，右侧区域有3个敌人，仅左侧符合条件。
示例2：
输入：
2 2 1
.E
E.
输出：
0
说明：整个区域敌人总数为2，不小于1。
示例3：
输入：
4 4 3
E.##
#.E#
##.#
.E.E
输出：
2
说明：两个区域的敌人数分别为1和2，均符合条件。
综合分析
- 时间复杂度：
O(N×M)。每个位置最多被访问一次，BFS队列的总体操作次数为线性。 - 空间复杂度：
O(N×M)。存储地图和标记数组需要线性空间。 - 算法选择：
- BFS 适合处理二维网格的连通区域问题，避免递归栈溢出。
- 队列操作天然适合逐层扩展，确保每个区域被完整遍历。
- 实现优化：
- 使用
emplace直接构造pair，避免不必要的拷贝。 - 方向数组简化了代码逻辑，提高可读性。
- 使用
- 适用场景：所有需要统计连通区域特性的问题（如岛屿数量、区域面积等）。
C
问题分析
我们需要统计战场地图中被墙壁分隔的各个区域中，敌人数小于给定阈值 K 的区域数量。每个区域由上下左右相邻的空地（包括敌人所在位置）组成，需遍历每个区域并统计其中的敌人数。
解题思路
- 输入处理：读取地图的行数
N、列数M和阈值K，并将地图存储为二维数组。 - 遍历地图：用双重循环遍历每个位置。
- 区域标记与统计：对每个未被访问且非墙壁的位置，使用 广度优先搜索（BFS） 遍历整个区域，统计敌人数。
- 判断条件：若当前区域敌人数
< K，则计入结果。 - 输出结果：统计并输出符合条件的区域数量。
代码实现
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100
int main() {
int N, M, K;
char grid[MAX_SIZE][MAX_SIZE]; // 存储地图
int visited[MAX_SIZE][MAX_SIZE] = {0}; // 标记是否访问过
int queue_x[MAX_SIZE * MAX_SIZE], queue_y[MAX_SIZE * MAX_SIZE]; // BFS队列
int front, rear; // 队列指针
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 方向数组
// 读取输入参数
scanf("%d %d %d", &N, &M, &K);
// 读取地图数据
for (int i = 0; i < N; i++) {
scanf("%s", grid[i]);
}
int count = 0; // 符合条件的区域数量
// 遍历每个位置
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// 跳过已访问或墙壁的位置
if (grid[i][j] == '#' || visited[i][j]) continue;
// BFS初始化
front = 0;
rear = 0;
queue_x[rear] = i;
queue_y[rear] = j;
rear++;
visited[i][j] = 1;
int enemy_count = (grid[i][j] == 'E') ? 1 : 0;
// BFS遍历
while (front < rear) {
int x = queue_x[front];
int y = queue_y[front];
front++;
// 遍历四个方向
for (int d = 0; d < 4; d++) {
int nx = x + dirs[d][0];
int ny = y + dirs[d][1];
// 检查新坐标是否合法
if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
// 跳过已访问或墙壁
if (!visited[nx][ny] && grid[nx][ny] != '#') {
visited[nx][ny] = 1;
if (grid[nx][ny] == 'E') enemy_count++;
queue_x[rear] = nx;
queue_y[rear] = ny;
rear++;
}
}
}
}
// 判断当前区域的敌人数是否小于K
if (enemy_count < K) count++;
}
}
// 输出结果
printf("%d\n", count);
return 0;
}
代码详细解析
输入处理：
scanf("%d %d %d", &N, &M, &K)：读取第一行的三个整数。- 循环读取
N行地图数据，存储到二维字符数组grid中。
标记数组：
visited是一个N×M的整型数组，初始化为全0，表示每个位置是否被访问过。
方向数组：
dirs定义四个移动方向（上、下、左、右），用于遍历相邻位置。
双重循环遍历地图：
- 外层循环遍历行
i，内层循环遍历列j。 - 如果当前位置是墙壁
#或已访问过，则跳过。
- 外层循环遍历行
BFS初始化：
- 使用队列数组
queue_x和queue_y存储坐标。 - 起始位置
(i, j)入队，并标记为已访问。 enemy_count统计当前区域的敌人数，初始化为当前坐标是否为敌人。
- 使用队列数组
BFS遍历：
- 从队列中取出坐标
(x, y)。 - 遍历四个方向，计算新坐标
(nx, ny)。 - 检查新坐标是否合法（不越界、未被访问且不是墙壁）。
- 如果是敌人
E，则敌人数+1，并将新坐标入队。
- 从队列中取出坐标
判断条件：
- 遍历完一个区域后，若
enemy_count < K，则符合条件的区域数count加一。
- 遍历完一个区域后，若
示例测试
示例1：
输入：
3 5 2
..#EE
E.#E.
###..
输出：
1
说明：左侧区域有1个敌人，右侧区域有3个敌人，仅左侧符合条件。
示例2：
输入：
2 2 1
.E
E.
输出：
0
说明：整个区域敌人总数为2，不小于1。
示例3：
输入：
4 4 3
E.##
#.E#
##.#
.E.E
输出：
2
说明：两个区域的敌人数分别为1和2，均符合条件。
综合分析
- 时间复杂度：
O(N×M)。每个位置最多被访问一次，BFS队列的总体操作次数为线性。 - 空间复杂度：
O(N×M)。存储地图和标记数组需要线性空间。 - 算法选择：
- BFS 适合处理二维网格的连通区域问题，避免递归栈溢出。
- 队列操作天然适合逐层扩展，确保每个区域被完整遍历。
- 实现优化：
- 使用数组模拟队列，避免动态内存分配。
- 立即标记已访问的格子，避免重复入队。
- 适用场景：所有需要统计连通区域特性的问题（如岛屿数量、区域面积等）。
GO
问题分析
我们需要统计战场地图中被墙壁分隔的各个区域中，敌人数小于给定阈值 K 的区域数量。每个区域由上下左右相邻的空地（包括敌人所在位置）组成，需遍历每个区域并统计其中的敌人数。
解题思路
- 输入处理：读取地图的行数
N、列数M和阈值K，并将地图存储为二维数组。 - 遍历地图：用双重循环遍历每个位置。
- 区域标记与统计：对每个未被访问且非墙壁的位置，使用 广度优先搜索（BFS） 遍历整个区域，统计敌人数。
- 判断条件：若当前区域敌人数
< K，则计入结果。 - 输出结果：统计并输出符合条件的区域数量。
代码实现
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
// 读取输入参数
var N, M, K int
fmt.Scanf("%d %d %d\n", &N, &M, &K)
// 初始化地图和标记数组
scanner := bufio.NewScanner(os.Stdin)
grid := make([][]byte, N)
visited := make([][]bool, N)
for i := 0; i < N; i++ {
scanner.Scan()
line := scanner.Text()
grid[i] = []byte(line)
visited[i] = make([]bool, M)
}
count := 0 // 符合条件的区域数量
dirs := [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // 方向数组
// 遍历每个位置
for i := 0; i < N; i++ {
for j := 0; j < M; j++ {
// 跳过已访问或墙壁的位置
if grid[i][j] == '#' || visited[i][j] {
continue
}
// BFS初始化
queue := [][2]int{{i, j}}
visited[i][j] = true
enemyCount := 0
// 统计起始位置的敌人
if grid[i][j] == 'E' {
enemyCount++
}
// BFS遍历
for len(queue) > 0 {
x, y := queue[0][0], queue[0][1]
queue = queue[1:] // 弹出队列头部
// 遍历四个方向
for _, d := range dirs {
nx, ny := x+d[0], y+d[1]
// 检查新坐标是否合法
if nx >= 0 && nx < N && ny >= 0 && ny < M {
// 跳过已访问或墙壁
if !visited[nx][ny] && grid[nx][ny] != '#' {
visited[nx][ny] = true
if grid[nx][ny] == 'E' {
enemyCount++
}
queue = append(queue, [2]int{nx, ny})
}
}
}
}
// 判断是否满足条件
if enemyCount < K {
count++
}
}
}
// 输出结果
fmt.Println(count)
}
代码详细解析
输入处理：
fmt.Scanf读取第一行的三个整数N、M、K。bufio.Scanner逐行读取地图数据，存储到二维字节数组grid中。
初始化：
visited是一个N×M的布尔数组，初始化为false，标记已访问的位置。
方向数组：
dirs定义四个移动方向（上、下、左、右），用于遍历相邻位置。
双重循环遍历地图：
- 外层循环遍历行
i，内层循环遍历列j。 - 跳过已访问或墙壁的位置。
- 外层循环遍历行
BFS初始化：
- 队列初始化为包含起始坐标
[i, j]，并标记为已访问。 enemyCount统计当前区域的敌人数，起始位置为敌人则初始化为 1。
- 队列初始化为包含起始坐标
BFS遍历：
- 从队列头部取出坐标
(x, y)。 - 遍历四个方向，计算新坐标
(nx, ny)。 - 若新坐标合法且未被访问，则标记为已访问，并统计敌人数量。
- 从队列头部取出坐标
判断条件：
- 遍历完一个区域后，若敌人数
< K，则count加一。
- 遍历完一个区域后，若敌人数
示例测试
示例1：
输入：
3 5 2
..#EE
E.#E.
###..
输出：
1
说明：左侧区域有1个敌人，右侧区域有3个敌人，仅左侧符合条件。
示例2：
输入：
2 2 1
.E
E.
输出：
0
说明：整个区域敌人总数为2，不小于1。
示例3：
输入：
4 4 3
E.##
#.E#
##.#
.E.E
输出：
2
说明：两个区域的敌人数分别为1和2，均符合条件。
综合分析
- 时间复杂度：
O(N×M)，每个位置最多被访问一次。 - 空间复杂度：
O(N×M)，存储地图和标记数组。 - 算法选择：
- BFS 天然适合处理网格连通区域问题，避免递归栈溢出。
- 使用队列逐层扩展，确保每个区域被完整遍历。
- 实现优化：
- 用
slice模拟队列，避免动态内存分配。 - 立即标记已访问的格子，避免重复入队。
- 用
- 适用场景：所有需要统计连通区域特性的问题（如岛屿数量、区域面积等）。
更多内容：
https://www.kdocs.cn/l/cvk0eoGYucWA
本文发表于【纪元A梦】，关注我，获取更多实用教程/资源！