c++(28ms 100%) Hamilton path with BFS
Runtime: 28 ms, faster than 100.00% of C++ online submissions for Detonate the Maximum Bombs.\nMemory Usage: 20.4 MB, less than 53.85% of C++ online submissions
Runtime: 28 ms, faster than 100.00% of C++ online submissions for Detonate the Maximum Bombs.\nMemory Usage: 20.4 MB, less than 53.85% of C++ online submissions for Detonate the Maximum Bombs.\n```\nclass Solution {\npublic:\n  int maximumDetonation(vector<vector<int>>& b) {\n    int n = b.size(), answer = 1;\n    vector<vector<int>>g(n);\n    \n    for(int i = 0; i != n; i++){\n      long R = (long)b[i][2] * b[i][2];\n      for(int j = i+1; j != n; j++){\n        long dx = b[j][0] - b[i][0], dy = b[j][1] - b[i][1];\n        long r = (long)b[j][2] * b[j][2];\n        long d = dx*dx + dy*dy;\n        if( d <= R) g[i].push_back(j);\n        if( d <= r) g[j].push_back(i);\n      }\n    }\n    \n    for(int i = 0; i != n && answer != n; i++){\n      vector<int>vis;\n      vis.clear();\n      vis.resize(n,0);\n      queue<int>q;\n      q.push(i);\n    \n      int k = 0;\n      while(!q.empty()){\n        int t = q.front(); q.pop();\n        if(vis[t]) continue;\n        vis[t] = 1, k++;\n          \n        for(auto next: g[t]) if(vis[next] == 0) q.push(next);\n      }\n      answer = max<int>(answer, k);\n    }\n    \n    return answer;\n  }\n};\n```\n\n**when I was solving contest I tried to solve this proublem with greedy algo , but it pass only 153 tests from 157 (very pity)**\n```\nclass Solution {\npublic:\n  static bool comp(vector<int> &a, vector<int>&b){\n    return a[2] > b[2];\n  }\n  \n  int maximumDetonation(vector<vector<int>>& b) {\n    sort(b.begin(), b.end(), comp);\n    int n = b.size(), answer = 1;\n    vector<int>vis(n,0);\n    \n    for(int i = 0; i != n; i++)\n      if(vis[i] == 0){\n        vis[i] = 1;\n        vector<vector<int>>v;\n        v.push_back(b[i]);\n        for(int j = 0; j != v.size(); j++){\n          long R = (long)v[j][2] * v[j][2]; \n          for(int k = 0; k != n; k++)\n            if(vis[k] == 0){\n            long dx = v[j][0] - b[k][0], dy = v[j][1] - b[k][1];\n            if( dx*dx + dy*dy <= R)\n              vis[k] = 1, v.push_back(b[k]);  \n          }\n        }  \n        answer = max<int>(answer, v.size());\n        v.clear();\n      }\n    \n    return answer;\n  }\n};\n```
['C', 'C++']