forked from AnasImloul/Leetcode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDetonate the Maximum Bombs.js
44 lines (40 loc) · 1.34 KB
/
Detonate the Maximum Bombs.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* @param {number[][]} bombs
* @return {number}
*/
var maximumDetonation = function(bombs) {
if(bombs.length <= 1) return bombs.length;
let adj = {}, maxSize = 0;
const checkIfInsideRange = (x, y, center_x, center_y, radius) =>{
return ( (x-center_x)**2 + (y-center_y)**2 <= radius**2 )
}
//CREATE ADJACENCY MATRIX
for(let i = 0;i<bombs.length;i++){
for(let j = i+1;j<bombs.length;j++){
if(!adj[i]) adj[i] = [];
if(!adj[j]) adj[j] = [];
let bombOne = bombs[i];
let bombTwo = bombs[j];
let fir = checkIfInsideRange(bombOne[0], bombOne[1], bombTwo[0], bombTwo[1], bombOne[2]);
if(fir) adj[i].push(j);
let sec = checkIfInsideRange(bombOne[0], bombOne[1], bombTwo[0], bombTwo[1], bombTwo[2]);
if(sec) adj[j].push(i);
}
}
//DEPTH FIRST SEARCH TO FIND ALL BOMBS TRIGGERED BY NODE
const dfs = (node, visited)=>{
let detonated = 1;
visited[node] = true;
let childs = adj[node] || []
for(let child of childs){
if(visited[child]) continue;
detonated += dfs(child, visited)
}
maxSize = Math.max(maxSize, detonated)
return detonated;
}
for(let i = 0 ;i<bombs.length;i++){
dfs(i, {})
}
return maxSize
};