2101. Detonate the Maximum Bombs

Medium
Description

給定一組炸彈 bombs[i] = [x, y, r]，代表位置 (x, y) 和爆炸半徑 r。引爆一顆炸彈會連鎖引爆其爆炸範圍內的其他炸彈。求引爆一顆炸彈最多能引爆多少顆炸彈。

Example:

Input: bombs = [[2,1,3],[6,1,4]] Output: 2

Intuition#

建立有向圖（A 能炸到 B 不代表 B 能炸到 A），對每個節點做 DFS/BFS 計算可達節點數。

  • 炸彈 A 能引爆 B 當且僅當 B 在 A 的爆炸半徑內
  • 這是有向關係（A 炸到 B 不代表 B 能炸到 A）
  • 對每個起點做 DFS/BFS，找最大可達節點數

Approaches#

⭐1: 建圖 + DFS#

  • 概念: 建立有向圖，對每個炸彈做 DFS 計算連鎖引爆數量，取最大值
  • 時間複雜度: O(n^3)，建圖 O(n^2)，n 次 DFS 每次 O(n)
  • 空間複雜度: O(n^2)
class Solution {
    fun maximumDetonation(bombs: Array<IntArray>): Int {
        val n = bombs.size
        val graph = Array(n) { mutableListOf<Int>() }

        for (i in 0 until n) {
            for (j in 0 until n) {
                if (i == j) continue
                val dx = bombs[i][0].toLong() - bombs[j][0]
                val dy = bombs[i][1].toLong() - bombs[j][1]
                val r = bombs[i][2].toLong()
                if (dx * dx + dy * dy <= r * r) {
                    graph[i].add(j)
                }
            }
        }

        var maxCount = 0
        for (i in 0 until n) {
            val visited = BooleanArray(n)
            maxCount = maxOf(maxCount, dfs(graph, i, visited))
        }
        return maxCount
    }

    private fun dfs(graph: Array<MutableList<Int>>, node: Int, visited: BooleanArray): Int {
        visited[node] = true
        var count = 1
        for (next in graph[node]) {
            if (!visited[next]) {
                count += dfs(graph, next, visited)
            }
        }
        return count
    }
}

2: BFS#

  • 概念: 同樣的思路用 BFS 實現
  • 時間複雜度: O(n^3)
  • 空間複雜度: O(n^2)
class Solution {
    fun maximumDetonation(bombs: Array<IntArray>): Int {
        val n = bombs.size
        val graph = Array(n) { mutableListOf<Int>() }

        for (i in 0 until n) {
            for (j in 0 until n) {
                if (i == j) continue
                val dx = bombs[i][0].toLong() - bombs[j][0]
                val dy = bombs[i][1].toLong() - bombs[j][1]
                val r = bombs[i][2].toLong()
                if (dx * dx + dy * dy <= r * r) {
                    graph[i].add(j)
                }
            }
        }

        var maxCount = 0
        for (start in 0 until n) {
            val visited = BooleanArray(n)
            val queue = ArrayDeque<Int>()
            queue.add(start)
            visited[start] = true
            var count = 0
            while (queue.isNotEmpty()) {
                val node = queue.removeFirst()
                count++
                for (next in graph[node]) {
                    if (!visited[next]) {
                        visited[next] = true
                        queue.add(next)
                    }
                }
            }
            maxCount = maxOf(maxCount, count)
        }
        return maxCount
    }
}

🔑 Takeaways#

  • Pattern: 有向圖可達性 – 對每個起點找最大可達集合
  • 關鍵技巧: 距離比較用 dx*dx + dy*dy <= r*r 避免浮點數誤差；注意用 Long 防止 Int 溢出