Leetcode引爆最多炸弹问题：Python代码特定测试用例错误排查

问题概述 #

给定一组炸弹，每个炸弹以自身位置为圆心、半径ri为范围的圆形区域，引爆一个炸弹后会连锁触发范围内的所有炸弹，求仅引爆一个炸弹时能引爆的最大数量。

编写的代码可通过大部分测试用例，但在测试用例[[634,440,278],[748,509,396],[995,881,251],[704,214,341],[832,972,238],[987,384,156],[378,988,402],[743,557,252],[814,868,196],[131,922,199],[13,398,444],[464,607,241],[426,128,81]]上出现错误：预期结果为12，代码输出为10。

原代码 #

import math
from typing import List

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        maxDetonations = 0
        for i in bombs:
            detonated = [i]
            undetonated = [bomb for bomb in bombs if bomb != i]
            for bomb in undetonated:
                if Solution.dist(i, bomb) <= i[2]:
                    detonated.append(bomb)
                    undetonated.remove(bomb)
            for bomb in detonated:
                for b in undetonated:
                    if Solution.dist(bomb, b) <= bomb[2]:
                        detonated.append(b)
                        undetonated.remove(b)
            
            if len(bombs) - len(undetonated) > maxDetonations:
                maxDetonations = len(bombs) - len(undetonated)

            print(maxDetonations, detonated)    
        return maxDetonations    

    @staticmethod
    def dist(cod1, cod2):
        return math.sqrt(math.pow(cod1[0] - cod2[0], 2) + math.pow(cod1[1] - cod2[1], 2))

错误分析 #

• 遍历列表时修改结构导致元素遗漏：在for bomb in undetonated循环中直接调用undetonated.remove(bomb)，会改变列表长度与元素索引，导致后续部分炸弹被跳过检查，无法触发连锁反应。
• 连锁触发逻辑不完整：代码仅执行两轮触发（初始炸弹一轮、初始触发的炸弹一轮），但连锁引爆是持续的过程——新加入引爆列表的炸弹也需要继续检查其可触发的炸弹，当前逻辑无法覆盖深层连锁。
• 元素直接比较存在风险：用bomb != i判断是否为初始炸弹，若存在完全相同的炸弹会错误排除，应该用索引区分每个炸弹。
• 距离计算的精度与效率问题：使用math.sqrt会引入浮点精度误差，且开根号运算冗余，实际只需比较距离平方与半径平方即可判断是否在范围内。

修正方案（BFS实现） #

import math
from typing import List
from collections import deque

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        max_count = 0
        
        # 预处理邻接表：存储每个炸弹能直接触发的其他炸弹索引
        adj = [[] for _ in range(n)]
        for i in range(n):
            x1, y1, r1 = bombs[i]
            r1_sq = r1 ** 2
            for j in range(n):
                if i == j:
                    continue
                x2, y2, _ = bombs[j]
                dx = x1 - x2
                dy = y1 - y2
                dist_sq = dx ** 2 + dy ** 2
                if dist_sq <= r1_sq:
                    adj[i].append(j)
        
        # 对每个炸弹执行BFS，统计连锁引爆总数
        for i in range(n):
            visited = [False] * n
            q = deque()
            q.append(i)
            visited[i] = True
            count = 1
            
            while q:
                curr = q.popleft()
                for neighbor in adj[curr]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        count += 1
                        q.append(neighbor)
            
            if count > max_count:
                max_count = count
        
        return max_count

修正说明 #

• 基于索引处理：用索引标记每个炸弹，避免元素比较的风险，同时构建邻接表存储触发关系，逻辑更清晰。
• BFS完整覆盖连锁触发：通过广度优先搜索持续处理新引爆的炸弹，直到没有新炸弹被触发，确保所有连锁反应都被统计。
• 优化距离计算：比较距离平方与半径平方，避免开根号的精度损失和性能消耗。

内容的提问来源于stack exchange，提问作者Ultimate48