Leetcode | Detonate the Maximum Bombs | Kotlin

devstromo · devstromo · commit b1866a15e429 · 2025-04-11T23:13:06.000-03:00
diff --git a/leetcode/src/main/kotlin/com/devstromo/medium/p2101/SolutionKt.kt b/leetcode/src/main/kotlin/com/devstromo/medium/p2101/SolutionKt.kt
@@ -1,5 +1,7 @@
 package com.devstromo.medium.p2101
 
+import kotlin.math.pow
+
 class SolutionKt {
     fun maximumDetonation(bombs: Array<IntArray>): Int {
         val n = bombs.size
@@ -31,6 +33,42 @@ class SolutionKt {
         return max
     }
 
+    fun maximumDetonationBest(bombs: Array<IntArray>): Int {
+        val graph = Array(bombs.size) { arrayListOf<Int>() }.apply {
+            for (i in 0..<bombs.size - 1) {
+                val (xi, yi, ri) = bombs[i]
+
+                for (j in i + 1..<bombs.size) {
+                    val (xj, yj, rj) = bombs[j]
+
+                    if ((xj - xi).toDouble().pow(2.0) + (yj - yi).toDouble().pow(2.0) <= ri.toDouble()
+                            .pow(2.0)
+                    ) get(i).add(j)
+                    if ((xi - xj).toDouble().pow(2.0) + (yi - yj).toDouble().pow(2.0) <= rj.toDouble()
+                            .pow(2.0)
+                    ) get(j).add(i)
+                }
+            }
+        }
+        var maxD = 0
+        for (i in bombs.indices) {
+            maxD = maxOf(maxD, dfs(i, graph, BooleanArray(bombs.size)))
+            if (maxD == bombs.size) break
+        }
+        return maxD
+    }
+
+    fun dfs(bomb: Int, graph: Array<ArrayList<Int>>, exploded: BooleanArray): Int {
+        if (exploded[bomb]) return 0
+
+        exploded[bomb] = true
+        var explosions = 1
+
+        for (b in graph[bomb]) explosions += dfs(b, graph, exploded)
+
+        return explosions
+    }
+
     private fun dfs(current: Int, graph: Array<MutableList<Int>>, visited: BooleanArray): Int {
         visited[current] = true
         var count = 1
diff --git a/leetcode/src/test/kotlin/com/devstromo/medium/p2101/SolutionKtUnitTest.kt b/leetcode/src/test/kotlin/com/devstromo/medium/p2101/SolutionKtUnitTest.kt
@@ -46,4 +46,45 @@ class SolutionKtUnitTest {
             )
         )
     }
+
+    @Test
+    fun `Test Detonate the Maximum Bombs Best`() {
+        assertEquals(
+            2, solution.maximumDetonationBest(
+                arrayOf(
+                    intArrayOf(2, 1, 3),
+                    intArrayOf(6, 1, 4),
+                )
+            )
+        )
+        assertEquals(
+            1, solution.maximumDetonationBest(
+                arrayOf(
+                    intArrayOf(1, 1, 5),
+                    intArrayOf(10, 10, 5),
+                )
+            )
+        )
+        assertEquals(
+            5, solution.maximumDetonationBest(
+                arrayOf(
+                    intArrayOf(1, 2, 3),
+                    intArrayOf(2, 3, 1),
+                    intArrayOf(3, 4, 2),
+                    intArrayOf(4, 5, 3),
+                    intArrayOf(5, 6, 4)
+                )
+            )
+        )
+
+        assertEquals(
+            1,
+            solution.maximumDetonationBest(
+                arrayOf(
+                    intArrayOf(1, 1, 100000),
+                    intArrayOf(100000, 100000, 1)
+                )
+            )
+        )
+    }
 }
