diff options
Diffstat (limited to 'detonate_max_bombs.cpp')
-rw-r--r-- | detonate_max_bombs.cpp | 61 |
1 files changed, 0 insertions, 61 deletions
diff --git a/detonate_max_bombs.cpp b/detonate_max_bombs.cpp deleted file mode 100644 index 4d92b98..0000000 --- a/detonate_max_bombs.cpp +++ /dev/null @@ -1,61 +0,0 @@ -// 2101. Detonate the Maximum Bombs -#include "leetcode.h" - -/* - * given a list of bombs. the range of a bomb is defined as the area where its - * effect can be felt. this area is in the shape of a circle with the center as - * the location of the bomb. the bombs are represented by a 0-indexed 2d integer - * array 'bombs' where 'bombs[i] = [xi, yi, ri]'. 'xi' and 'yi' denote the x and - * y coordinates of the location of the i'th bomb, whereas 'ri' denotes the - * radius of its range. you may choose to detonate a single bomb. when a bomb is - * detonated, it will detonate all the bombs that lie in its range. these bombs - * will further detonate the bombs that lie in their ranges. given the list of - * 'bombs', return the max number of bombs that can be detonated - */ - -class Solution { - void dfs(vvd & graph, vector<bool> &visited, int c, int i) { - visited[i] = true; - c++; - for (int j = 0; j < graph[i].size(); j++) - if (!visited[graph[i][j]]) - dfs(graph, visited, c, graph[i][j]); - } - -public: - int maximumDetonation(vvd & bombs) { - int n = bombs.size(), ans = INT_MIN; - vvd graph(n); - for (int i = 0; i < n; i++) { - long long int x1, y1, r1; - x1 = bombs[i][0]; - y1 = bombs[i][1]; - r1 = bombs[i][2]; - for (int j = 0; j < n; j++) - if (i != j) { - long long int x2, y2, r2; - x2 = abs(x1 - bombs[j][0]); - y2 = abs(y1 - bombs[j][1]); - if (x2 * x2 + y2 * y2 <= r1 * r1) - graph[i].push_back(j); - } - } - for (int i = 0; i < n; i++) { - int c = 0; - vector<bool> visited(n, false); - dfs(graph, visited, c, i); - ans = max(ans, c); - } - return ans; - } -}; - -int main() { - Solution obj; - vvd b1 = {{2, 1, 3}, {6, 1, 4}}; - vvd b2 = {{1, 1, 5}, {10, 10, 5}}; - vvd b3 = {{1, 2, 3}, {2, 3, 1}, {3, 4, 2}, {4, 5, 3}, {5, 6, 4}}; - printf("%d\n", obj.maximumDetonation(b1)); // expect: 2 - printf("%d\n", obj.maximumDetonation(b2)); // expect: 1 - printf("%d\n", obj.maximumDetonation(b3)); // expect: 5 -} |