1. 题目背景与核心需求解析这道来自华为OD机试的编程题战场索敌·区域统计问题属于典型的图论与搜索算法应用场景。题目模拟了战场侦察场景需要统计战场地图中特定条件的敌军分布区域数量。1.1 问题场景还原假设我们获得了一张M×N的战场二维矩阵地图其中每个单元格可能是敌军用特定字符表示如E也可能是空地用另一个字符表示如.相邻的敌军单元上下左右方向组成一个敌军区域需要统计所有包含敌军数量小于K的区域的个数这种区域统计问题在实际开发中非常常见比如图像处理中的连通区域分析、游戏开发中的地图探索算法等。1.2 输入输出规范典型输入格式示例3 3 2 // 地图行数、列数、阈值K E E E . E . . . E预期输出2表示有2个敌军区域的数量小于K22. 解题思路与算法选择2.1 基础思路分析这个问题本质上是要遍历整个二维矩阵对每个未被访问过的敌军单元进行区域探索统计每个区域的敌军单元数量比较该数量与阈值K的关系2.2 算法选型对比常见的解决方案有三种算法类型时间复杂度空间复杂度适用场景深度优先搜索(DFS)O(M×N)O(M×N)递归实现简洁但大数据可能栈溢出广度优先搜索(BFS)O(M×N)O(M×N)队列实现适合大规模数据并查集(Disjoint Set)O(M×N α(M×N))O(M×N)适合动态连通性问题对于机试场景推荐使用BFS因为非递归实现更稳定代码结构清晰易于调试时间复杂度与DFS相同但更可控3. Python实现详解3.1 基础实现框架from collections import deque def count_regions(matrix, m, n, k): visited [[False for _ in range(n)] for _ in range(m)] directions [(-1,0),(1,0),(0,-1),(0,1)] result 0 for i in range(m): for j in range(n): if matrix[i][j] E and not visited[i][j]: region_size 0 queue deque() queue.append((i,j)) visited[i][j] True while queue: x, y queue.popleft() region_size 1 for dx, dy in directions: nx, ny x dx, y dy if 0 nx m and 0 ny n: if matrix[nx][ny] E and not visited[nx][ny]: visited[nx][ny] True queue.append((nx, ny)) if region_size k: result 1 return result3.2 关键代码解析visited矩阵记录每个单元格是否已被访问避免重复统计directions数组定义四个移动方向上、下、左、右双重循环遍历整个矩阵寻找未被访问的敌军单元BFS队列使用deque实现高效的队列操作边界检查确保不会访问越界的位置3.3 性能优化技巧原地标记可以用特殊字符如V直接修改原矩阵来标记访问节省visited矩阵空间提前终止当region_size ≥ K时可以直接终止当前区域的BFS输入优化对于Python使用sys.stdin读取大数据量输入更高效4. JavaScript实现方案4.1 完整实现代码function countRegions(matrix, m, n, k) { const visited Array(m).fill().map(() Array(n).fill(false)); const directions [[-1,0],[1,0],[0,-1],[0,1]]; let result 0; for(let i0; im; i) { for(let j0; jn; j) { if(matrix[i][j] E !visited[i][j]) { let regionSize 0; const queue [[i,j]]; visited[i][j] true; while(queue.length 0) { const [x,y] queue.shift(); regionSize; for(const [dx,dy] of directions) { const nx x dx, ny y dy; if(nx0 nxm ny0 nyn) { if(matrix[nx][ny] E !visited[nx][ny]) { visited[nx][ny] true; queue.push([nx,ny]); } } } } if(regionSize k) result; } } } return result; }4.2 JS特有注意事项队列性能JS数组的shift()操作是O(n)复杂度对于大规模数据建议实现循环队列矩阵初始化不能用Array(m).fill(Array(n).fill(false))这会导致行引用相同解构赋值const [x,y] queue.shift()使代码更简洁5. 边界条件与测试用例设计5.1 必须考虑的边界情况全敌军地图所有单元格都是E全空地图所有单元格都是.单行或单列的特殊地图K0或K1的特殊情况最大规模测试如1000×1000矩阵5.2 测试用例示例# 测试用例1常规情况 m,n,k 3,3,2 matrix [ [E,E,E], [.,E,.], [.,.,E] ] assert count_regions(matrix,m,n,k) 2 # 测试用例2全空地图 m,n,k 2,2,1 matrix [ [.,.], [.,.] ] assert count_regions(matrix,m,n,k) 0 # 测试用例3K1特殊情况 m,n,k 3,3,1 matrix [ [E,.,E], [.,.,.], [E,.,E] ] assert count_regions(matrix,m,n,k) 46. 常见错误与调试技巧6.1 典型错误模式无限循环忘记标记已访问节点导致重复访问越界访问未检查数组边界直接访问相邻单元方向遗漏少写了某个移动方向导致区域不完整初始化错误visited矩阵初始化不正确特别是JS中6.2 调试建议打印中间状态在BFS过程中打印队列和visited矩阵小规模测试先用3×3等小矩阵验证基本逻辑可视化调试将矩阵和访问状态图形化输出边界测试专门测试单行、单列、全空等特殊情况7. 算法扩展与变种思考7.1 问题变种8方向连通如果考虑斜对角方向相邻也算连通区域动态阈值不同区域可能有不同的K值多层级区域区分大区域和小区域的统计7.2 实际应用延伸图像处理连通区域分析可用于图像分割游戏开发地图探索和迷雾系统实现社交网络寻找小规模社群群体关键提示在华为OD机试中除了正确性外代码的可读性和规范性也很重要。建议添加适当的注释使用有意义的变量名处理所有可能的异常输入考虑时间/空间复杂度的优化空间8. 性能优化进阶对于超大规模矩阵如1e5×1e5需要考虑并行计算将矩阵分块并行处理内存优化使用位图表示visited矩阵迭代深化结合DFS和BFS的优点外部存储对无法装入内存的超大矩阵使用磁盘存储处理Python优化示例使用位运算标记访问状态def count_regions_optimized(matrix, m, n, k): visited 0 # 用整数位图表示访问状态 directions [(-1,0),(1,0),(0,-1),(0,1)] result 0 for i in range(m): for j in range(n): pos i * n j if matrix[i][j] E and not (visited (1 pos)): region_size 0 queue deque() queue.append((i,j)) visited | 1 pos while queue: x, y queue.popleft() region_size 1 for dx, dy in directions: nx, ny x dx, y dy if 0 nx m and 0 ny n: new_pos nx * n ny if matrix[nx][ny] E and not (visited (1 new_pos)): visited | 1 new_pos queue.append((nx, ny)) if region_size k: result 1 return result这种优化可以将空间复杂度从O(M×N)降低到O(1)但仅适用于较小规模的矩阵Python整数通常为64位。对于真正的大规模数据需要使用分块处理或其他高级算法。
