目录

题目

思路

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。让他帮助你查询原因。