华为OD机试：DFS/BFS算法实战之战场索敌区域统计

1. 题目背景与核心需求解析这道来自华为OD机试的编程题战场索敌·区域统计属于典型的图论与搜索算法应用场景。题目模拟了战场侦察场景需要从二维矩阵中统计特定条件的区域数量考察选手对深度优先搜索(DFS)或广度优先搜索(BFS)算法的掌握程度。1.1 问题场景还原假设我们有一个M×N的战场地图用二维矩阵表示。矩阵中的每个单元格可能是以下两种状态之一E代表敌军单位(Enemy).代表空地需要统计所有由E组成的连通区域数量其中连通区域定义为上下左右相邻的E单元格组成的集合。这与图像处理中的连通域分析、社交网络中的社群发现等实际问题具有相同的数学模型。1.2 输入输出规范典型输入格式示例3 3 E.E .EE ...表示3行3列的矩阵需要输出连通区域数量此例中为2个区域2. 算法设计与技术选型2.1 基础解法DFS/BFS遍历这是最直接的解决方案时间复杂度O(M×N)遍历矩阵中的每个单元格遇到未访问过的E时启动DFS/BFS标记所有连通E为已访问统计启动搜索的次数即为答案Python实现要点def count_regions(matrix): if not matrix: return 0 rows, cols len(matrix), len(matrix[0]) visited [[False for _ in range(cols)] for _ in range(rows)] count 0 def dfs(i, j): if i 0 or i rows or j 0 or j cols or matrix[i][j] ! E or visited[i][j]: return visited[i][j] True dfs(i1, j) dfs(i-1, j) dfs(i, j1) dfs(i, j-1) for i in range(rows): for j in range(cols): if matrix[i][j] E and not visited[i][j]: dfs(i, j) count 1 return count2.2 优化方向并查集(Union-Find)对于大规模数据可以考虑并查集实现将每个E单元格视为独立集合遍历时合并相邻E的集合最终统计独立集合数量JavaScript实现示例class UnionFind { constructor(size) { this.parent Array(size).fill().map((_, i) i); this.count size; } find(x) { while (this.parent[x] ! x) { this.parent[x] this.parent[this.parent[x]]; x this.parent[x]; } return x; } union(x, y) { const rootX this.find(x); const rootY this.find(y); if (rootX ! rootY) { this.parent[rootY] rootX; this.count--; } } } function countRegions(grid) { if (!grid.length) return 0; const m grid.length, n grid[0].length; const dummy m * n; // 虚拟节点 const uf new UnionFind(m * n 1); for (let i 0; i m; i) { for (let j 0; j n; j) { if (grid[i][j] E) { const index i * n j; // 检查四个方向 if (i 0 grid[i-1][j] E) uf.union(index, (i-1)*n j); if (j 0 grid[i][j-1] E) uf.union(index, i*n j-1); } } } // 统计独立E区域数量 const rootSet new Set(); for (let i 0; i m; i) { for (let j 0; j n; j) { if (grid[i][j] E) { rootSet.add(uf.find(i*n j)); } } } return rootSet.size; }3. 边界条件与特殊测试用例3.1 必须考虑的边界情况空矩阵输入应返回0全.矩阵应返回0全E矩阵应返回1单行或单列矩阵锯齿状输入各行长度不一致超大矩阵测试考察算法效率3.2 典型测试用例集test_cases [ ([], 0), # 空输入 ([.], 0), # 单点非E ([E], 1), # 单点E ([E.E, .E., E.E], 5), # 棋盘式分布 ([EEEE, E..E, EEEE], 1), # 环形连通 ([E.E.E, ....., E.E.E], 4), # 多行间隔 ([E*100 for _ in range(100)], 1) # 大规模全E ]4. 性能优化与工程实践4.1 空间复杂度优化原始DFS使用了O(M×N)的visited矩阵可以优化修改原矩阵将访问过的E改为其他字符如V位图压缩用bitset表示访问状态Python优化实现def count_regions_optimized(matrix): count 0 for i in range(len(matrix)): for j in range(len(matrix[0])): if matrix[i][j] E: dfs_optimized(matrix, i, j) count 1 return count def dfs_optimized(matrix, i, j): if 0 i len(matrix) and 0 j len(matrix[0]) and matrix[i][j] E: matrix[i][j] V # 标记为已访问 dfs_optimized(matrix, i1, j) dfs_optimized(matrix, i-1, j) dfs_optimized(matrix, i, j1) dfs_optimized(matrix, i, j-1)4.2 并行计算可能性对于超大规模矩阵如10000×10000可以考虑分块处理将矩阵划分为多个子块边界合并处理完子块后合并边界区域使用多线程或GPU加速5. 题目变种与扩展思考5.1 常见变种题型统计每个连通区域的大小找到最大的连通区域8连通方向下的区域统计动态更新矩阵后的实时统计三维空间中的连通区域统计5.2 实际工程应用图像处理连通组件标记游戏开发地图区域划分社交网络社群发现电路设计短路检测医学影像病灶区域分析6. 编码实现注意事项6.1 Python实现细节使用列表推导式初始化visited矩阵更高效将dfs函数定义在外部可减少嵌套函数调用开销使用itertools.product简化双重循环优化后的Python实现from itertools import product def count_regions_py(matrix): if not matrix: return 0 m, n len(matrix), len(matrix[0]) count 0 def dfs(i, j): stack [(i, j)] while stack: x, y stack.pop() if 0 x m and 0 y n and matrix[x][y] E: matrix[x][y] V stack.extend([(x1,y),(x-1,y),(x,y1),(x,y-1)]) for i, j in product(range(m), range(n)): if matrix[i][j] E: dfs(i, j) count 1 return count6.2 JavaScript实现技巧使用TypedArray处理大型矩阵更高效用队列实现BFS避免递归栈溢出使用位运算压缩状态JavaScript BFS实现function countRegionsBFS(grid) { if (!grid.length) return 0; const m grid.length, n grid[0].length; let count 0; for (let i 0; i m; i) { for (let j 0; j n; j) { if (grid[i][j] E) { count; const queue [[i,j]]; grid[i][j] V; while (queue.length) { const [x,y] queue.shift(); [[x1,y],[x-1,y],[x,y1],[x,y-1]].forEach(([nx,ny]) { if (nx0 nxm ny0 nyn grid[nx][ny]E) { grid[nx][ny] V; queue.push([nx,ny]); } }); } } } } return count; }7. 调试与验证方法7.1 单元测试编写Python unittest示例import unittest class TestRegionCount(unittest.TestCase): def test_empty(self): self.assertEqual(count_regions([]), 0) def test_single_E(self): self.assertEqual(count_regions([E]), 1) def test_complex_case(self): grid [ E.E.E, ....., E.E.E, ....., E.E.E ] self.assertEqual(count_regions(grid), 6) if __name__ __main__: unittest.main()7.2 可视化调试技巧对于复杂案例可以添加打印函数观察搜索过程def print_matrix(matrix): for row in matrix: print( .join(row)) print() def dfs_debug(matrix, i, j): if 0 i len(matrix) and 0 j len(matrix[0]) and matrix[i][j] E: matrix[i][j] str(count1) # 用不同数字标记不同区域 print_matrix(matrix) dfs_debug(matrix, i1, j) dfs_debug(matrix, i-1, j) dfs_debug(matrix, i, j1) dfs_debug(matrix, i, j-1)8. 复杂度分析与算法选择建议8.1 时间复杂度对比算法时间复杂度空间复杂度适用场景DFS递归O(M×N)O(M×N)常规规模矩阵DFS栈实现O(M×N)O(longest_path)避免递归深度问题BFS队列O(M×N)O(min(M,N))最短路相关问题时并查集O(M×N×α(MN))O(M×N)需要动态合并的场景8.2 选择建议面试场景推荐DFS递归实现代码简洁竞赛场景根据数据规模选择大矩阵用非递归实现工程实践考虑使用并查集特别是需要支持动态更新的场景特殊约束递归深度受限时改用BFS或栈式DFS