【华为OD机试真题】战场索敌 · 区域统计问题 (Java/Go)

一、题目题目描述有一个大小是 N*M 的战场地图被墙壁 # 分隔成大小不同的区域。上下左右四个方向相邻的空地 . 属于同一个区域。只有空地上可能存在敌人 E。请求出地图上总共有多少区域里的敌人数小于 K。输入描述第一行输入为 N, M, KN 表示地图的行数M 表示地图的列数K 表示目标敌人数量。N, M 100之后为一个 N×M 大小的字符数组。输出描述敌人数小于 K 的区域数量。示例1输入3 5 2 ..#EE E.#E. ###..输出1说明地图被墙壁分为两个区域左边区域有1个敌人右边区域有3个敌人符合条件的区域数量是1二、核心解题思路连通块搜索本题本质是图论中的连通分量计数问题的变种。我们需要遍历整个地图每当发现一个未访问过的非墙壁格子.或E就启动一次搜索DFS 或 BFS将该连通块内的所有格子标记为“已访问”并统计其中E的数量。步骤 1全局遍历使用双重循环遍历地图的每一个格子(i, j)。如果当前格子是#或已访问过跳过。如果当前格子是.或E且未访问说明发现了一个新区域。步骤 2启动搜索 (DFS/BFS)从当前格子出发向上下左右四个方向扩展边界检查不越界。合法性检查不是墙壁#且 未访问过。统计逻辑如果遇到E计数器count。标记将访问过的格子标记为true防止重复计算。步骤 3判定与累加搜索结束后得到该区域的敌人总数enemyCount。若enemyCount K结果ans。继续遍历地图寻找下一个未访问的区域。Java vs Go实现策略差异⚔️Java利用其面向对象特性代码结构清晰。DFS 递归写法非常简洁对于 100×100100×100 的地图递归深度最大 10000通常在 JVM 默认栈大小范围内代码可读性最高。Go强调性能与显式控制。虽然 Go 也支持递归但在处理网格问题时使用BFS 切片模拟队列是更“Go 风格”的做法完全避免栈溢出风险且内存分配更可控。三、Java 语言实现 (DFS 递归版)Java 的递归写法如同“探路者”代码逻辑与人类直觉高度一致极其优雅。import java.util.Scanner; public class BattlefieldRegions { // 方向数组上、下、左、右 private static final int[] dx {-1, 1, 0, 0}; private static final int[] dy {0, 0, -1, 1}; public static void main(String[] args) { Scanner scanner new Scanner(System.in); if (!scanner.hasNextInt()) return; int N scanner.nextInt(); int M scanner.nextInt(); int K scanner.nextInt(); char[][] grid new char[N][M]; for (int i 0; i N; i) { String line scanner.next(); grid[i] line.toCharArray(); } boolean[][] visited new boolean[N][M]; int validRegions 0; // 遍历每个格子 for (int i 0; i N; i) { for (int j 0; j M; j) { // 如果是墙壁或已访问跳过 if (grid[i][j] # || visited[i][j]) { continue; } // 发现新区域启动DFS统计敌人 int enemyCount dfs(grid, visited, i, j, N, M); // 判断是否符合条件 if (enemyCount K) { validRegions; } } } System.out.println(validRegions); scanner.close(); } /** * DFS 深度优先搜索 * 返回当前连通块内的敌人数量 */ private static int dfs(char[][] grid, boolean[][] visited, int x, int y, int N, int M) { // 标记当前点已访问 visited[x][y] true; int count 0; // 如果当前点是敌人计数1 if (grid[x][y] E) { count; } // 向四个方向探索 for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 边界检查 合法性检查 if (nx 0 nx N ny 0 ny M grid[nx][ny] ! # !visited[nx][ny]) { count dfs(grid, visited, nx, ny, N, M); } } return count; } }Java 代码亮点递归简洁dfs函数仅 20 行左右逻辑自包含无需手动维护栈结构。方向数组使用dx/dy数组简化四个方向的遍历代码避免写四遍if。状态隔离visited数组独立于grid保持原始数据不变符合函数式编程思想。四、Go 语言实现 (BFS 迭代版)Go 语言在处理此类问题时推荐使用BFS广度优先搜索配合slice模拟队列。这种方式不仅避免了深层递归可能导致的stack overflow虽然在本题规模下不太可能但这是良好的工程习惯而且执行效率极高。package main import ( bufio fmt os strings ) // 坐标结构体 type Point struct { x, y int } func main() { // 使用 bufio 提高读取效率 scanner : bufio.NewScanner(os.Stdin) if !scanner.Scan() { return } var N, M, K int fmt.Sscanf(scanner.Text(), %d %d %d, N, M, K) grid : make([][]rune, N) for i : 0; i N; i { if !scanner.Scan() { break } grid[i] []rune(scanner.Text()) } visited : make([][]bool, N) for i : range visited { visited[i] make([]bool, M) } validRegions : 0 // 方向数组 dx : []int{-1, 1, 0, 0} dy : []int{0, 0, -1, 1} // 遍历地图 for i : 0; i N; i { for j : 0; j M; j { // 跳过墙壁或已访问点 if grid[i][j] # || visited[i][j] { continue } // 发现新区域启动 BFS enemyCount : bfs(grid, visited, i, j, N, M, dx, dy) if enemyCount K { validRegions } } } fmt.Println(validRegions) } // BFS 广度优先搜索 func bfs(grid [][]rune, visited [][]bool, startX, startY, N, M int, dx, dy []int) int { count : 0 queue : []Point{{startX, startY}} visited[startX][startY] true // 如果起点是敌人先计数 if grid[startX][startY] E { count } head : 0 for head len(queue) { curr : queue[head] head // 探索四个方向 for k : 0; k 4; k { nx : curr.x dx[k] ny : curr.y dy[k] // 边界与合法性检查 if nx 0 nx N ny 0 ny M grid[nx][ny] ! # !visited[nx][ny] { visited[nx][ny] true if grid[nx][ny] E { count } // 入队 queue append(queue, Point{nx, ny}) } } } return count }Go 代码亮点结构体建模定义Point结构体存储坐标类型安全代码语义清晰。Slice 模拟队列利用 Go 切片动态扩容的特性append入队索引head出队无需引入container/list性能更佳。Rune 处理使用[]rune处理字符数组完美支持 Unicode虽然本题只有 ASCII但这体现了 Go 的严谨性。IO 优化使用bufio.Scanner替代fmt.Scan在处理多行输入时更稳定高效。五、逻辑推演与避坑指南示例1 深度推演输入3 5 2 ..#EE E.#E. ###..地图可视化(0,0). (0,1). | # (0,3)E (0,4)E (1,0)E (1,1). | # (1,3)E (1,4). ############### (全是墙) - 实际上是 ###.. 修正第三行###..区域划分左侧区域包含点(0,0), (0,1), (1,0), (1,1)敌人位置(1,0)是E。敌人总数1。判定12 (K)符合条件。右侧区域包含点(0,3), (0,4), (1,3), (1,4)敌人位置(0,3), (0,4), (1,3)是E。敌人总数3。判定3̸2 不符合。下方区域(第三行###..)看第二行对应列(1,3)是E,(1,4)是.。第三行(2,3),(2,4)是.。连通性检查(1,4)和(2,4)是上下相邻的修正推演右侧区域实际上包含了(2,3), (2,4)。点集(0,3)E, (0,4)E, (1,3)E, (1,4)., (2,3)., (2,4).。敌人总数依然是3。判定3̸2 。最终结果只有左侧区域符合输出1。⚠️ 常见陷阱输入读取Java 中scanner.next()会自动跳过空格和换行非常适合读取每一行的字符串。Go 中要注意scanner.Text()获取整行不要混用Scan和Text导致指针错位。边界条件地图边缘第 0 行、第 N-1 行等容易越界务必在 DFS/BFS 内部第一行做nx 0 nx N检查。重复访问必须在入队/递归前就标记visited true。如果在出队/回溯时才标记会导致同一个点被多次加入队列/栈造成死循环或超时。K 的值题目是“小于 K” ()不是“小于等于”。如果某区域敌人数正好是 K不应计入。六、复杂度分析时间复杂度 O(N×M) 。每个格子最多被访问一次进入 DFS/BFS 一次。每个格子的四个邻居检查是常数操作。空间复杂度 O(N×M) 。visited数组占用 N×M 。DFS 递归栈或 BFS 队列在最坏情况下整个地图是一个区域也可能达到 N×M 。七、结语“战场区域统计”是考察图论基础与代码实现细节的经典题目。Java 开发者可以学习如何用递归将复杂逻辑简化为优雅的几行代码。Go 开发者可以掌握如何用切片和结构体构建高效的迭代算法体现 Go 的性能优势。无论选择哪种语言“标记已访问”和“方向数组”都是解决此类网格问题的通用钥匙。掌握这套模板无论是 OD 机试还是 LeetCode 刷题都能游刃有余觉得有用请点赞、收藏⭐、关注后续将持续更新华为 OD 高频真题的多语言题解