2026 华为OD机试真题 7月26日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

在一款游戏中设计炸弹人技能效果是预埋地雷，当敌人从地雷上走过时会触发地雷爆炸造成伤害。

当一个地雷被引爆时，在一定距离内的相邻的地雷也会引爆，这些能够同时引爆的地雷形成一个雷区。一个雷区可以由一枚孤立的地雷组成，也可以由一片有连锁爆炸反应的多枚地雷组成。

现给出一组炸弹人地雷连锁爆炸关联数据，请计算有效雷区数量。

2026 华为OD机试真题 7月26日华为OD上机新系统考试真题 100 分题型

输入描述

地雷连锁爆炸关系数组 isChainExplosion：地雷连锁爆炸信息被记录在一个 n×n 的二维数组 isChainExplosion 中：

• isChainExplosion[i][j] = 1 表示第 i 枚地雷和第 j 枚地雷有互相引爆关系
• isChainExplosion[i][j] = 0 表示第 i 枚地雷和第 j 枚地雷不会被彼此引爆

输入用例保证：

• isChainExplosion[i][i] 和 isChainExplosion[j][j] 的值同时为 0 或者同时为 1
• 地雷数量在 [1,20] 之间

输出描述

有效雷区数量。

示例1

输入

[[1,0],[0,1]]

输出

2

说明

两枚地雷互相独立，其中一枚被引爆时不会触发另一枚地雷，所以雷区数量是 2

示例2

输入

[[1,0,0],[0,1,1],[0,1,1]]

输出

2

说明

一共三枚地雷，第一枚和第二、第三枚互相独立，第二枚和第三枚临近且引爆，因此雷区数量是 2

示例3

输入

[[1,1,1],[1,1,1],[1,1,1]]

输出

1

说明

全连通场景，三枚地雷两两直接互相引爆，形成一个雷区

解题思路

核心思想

把每一枚地雷看成图中的一个节点，isChainExplosion[i][j] = 1 表示节点 i 和节点 j 之间存在连锁爆炸关系。一个雷区就是图中的一个连通块。

因此，本题可以转化为：给定邻接矩阵，统计图中连通块的数量。

算法步骤

1. 按示例格式读取一行 JSON-like 二维矩阵。
2. 创建 visited 数组，记录每枚地雷是否已经归入某个雷区。
3. 从第 0 枚地雷开始遍历。
4. 如果当前地雷未访问过，则从它开始 DFS/BFS，把所有能连锁到的地雷都标记为已访问。
5. 每启动一次新的 DFS/BFS，就说明发现了一个新的雷区，答案加 1。
6. 遍历结束后输出答案。

复杂度分析

设地雷数量为 n。

• 邻接矩阵 DFS 需要检查每个节点到其他节点的关系，时间复杂度为 O(n^2)。
• visited 数组和递归/队列空间复杂度为 `O(