leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

2101.cpp (1127B)

      1 class Solution {
      2   public:
      3     int maximumDetonation(vector<vector<int>> &bombs) {
      4         vector<vector<int>> adj(bombs.size());
      5         for (int i = 0; i < bombs.size(); i++) {
      6             for (int j = i + 1; j < bombs.size(); j++) {
      7                 double dist = sqrt(pow(bombs[i][0] - bombs[j][0], 2) + pow(bombs[i][1] - bombs[j][1], 2));
      8                 if (dist <= bombs[i][2]) adj[i].push_back(j);
      9                 if (dist <= bombs[j][2]) adj[j].push_back(i);
     10             }
     11         }
     12 
     13         int maxi = INT_MIN;
     14         for (int i = 0; i < bombs.size(); i++) {
     15             vector<bool> visited(bombs.size(), false);
     16             int count = 0;
     17             stack<int> st;
     18             st.push(i);
     19             visited[i] = true;
     20             while (!st.empty()) {
     21                 int root = st.top();
     22                 st.pop();
     23                 count++;
     24                 for (int c : adj[root])
     25                     if (!visited[c]) {
     26                         visited[c] = true;
     27                         st.push(c);
     28                     }
     29             }
     30             maxi = max(maxi, count);
     31         }
     32 
     33         return maxi;
     34     }
     35 };