目录

题目

思路

Code

题目

题目内容：

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

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

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

地雷数量在 1 到 20 之间。输入用例保证对角线值同时为 0 或同时为 1。

输入描述：

输入 n 行，每行是一个长度为 n 的 0/1 数组，元素之间用英文逗号分隔，表示地雷连锁爆炸关系矩阵 isChainExplosion。

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

输出描述：

输出有效雷区数量。

样例 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

说明：

三枚地雷两两连通，形成一个雷区。

思路

整体思路：把每枚地雷看成图中的一个节点，互相引爆关系看成边，题目要求的雷区数量就是连通块数量。

第一步：读取矩阵后创建访问数组，记录每枚地雷是否已经归入某个雷区。

第二步：从头枚举每枚地雷，如果尚未访问，说明发现一个新雷区，计数加一。

第三步：从该地雷出发递归或迭代引爆所有可达地雷，并标记为已访问。

边界处理：即使某枚地雷与任何其他地雷都不相连，也会在枚举时单独形成一个雷区。

复杂度分析：矩阵规模为 n 乘 n，搜索时最多检查所有矩阵元素，时间复杂度 O(n^2)，空间复杂度 O(n)。

Code

import sys matrix = [list(map(int, line.strip().split(","))) for line in sys.stdin if line.strip()] n = len(matrix) visited = [False] * n def dfs(start): stack = [start] visited[start] = True while stack: node = stack.pop() for nxt, linked in enumerate(matrix[node]): # 只要存在连锁引爆关系，就归入同一个雷区继续扩展。 if linked == 1 and not visited[nxt]: visited[nxt] = True stack.append(nxt) count = 0 for i in range(n): if visited[i]: continue # 未访问节点代表发现一个新的雷区，即使孤立也要计数。 count += 1 dfs(i) # 输出最终连通块数量。 print(count)

JS

const fs = require("fs"); const lines = fs.readFileSync(0, "utf8").trim().split(/\n/).filter(Boolean); const matrix = lines.map(line => line.trim().split(",").map(Number)); const n = matrix.length; const visited = Array(n).fill(false); let count = 0; for (let i = 0; i < n; i++) { if (visited[i]) continue; // 每个未访问节点都是一个新雷区的起点。 count++; const stack = [i]; visited[i] = true; while (stack.length) { const node = stack.pop(); for (let next = 0; next < n; next++) { // 有连锁引爆关系就纳入当前雷区继续搜索。 if (matrix[node][next] === 1 && !visited[next]) { visited[next] = true; stack.push(next); } } } } // 雷区数量等于连通块数量。 console.log(count);

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。