目录题目思路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)。Codeimport 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)JSconst 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机试真题PythonJSJavaGo合集】【超值优惠】Py/JS/Java/Go合集【华为od机试真题Python】Python真题题库【华为od机试真题JavaScript】JavaScript真题题库【华为od机试真题JavaGo】JavaGo真题题库【华为od机试真题C】C真题题库【华为od机试真题C语言】C语言真题题库【华为od面试手撕代码题库】面试手撕代码题库【华为od机试面试交流群】【文章底部有二维码链接可扫码加交流群】华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。