C++ | DFS | Intuition and Code Explained
Explanation\nThe intuition is to keep checking the bombs we can detonate if we start from the i-th bomb. The conditions for detonation are:\n1. The bomb shouldn
### Explanation\nThe intuition is to keep checking the bombs we can detonate if we start from the i-th bomb. The conditions for detonation are:\n1. The bomb shouldn\'t be visited before (Except if that is the starting point).\n2. The distance between two points should be less than radius of the previous bomb, i.e, (x1-x2) * (y1-y2) <= r * r \n\nI have kept a visited array for every bomb and ans stores the maximum count. \n\n\n\n**Please upvote if this post helped you!** If you have any queries, you can comment below. I would be happy to help!\n\n### Code\n```\nclass Solution {\npublic:\n    bool check(long long x1,long long  x2, long long  y1,long long  y2,long long  r)\n    {\n        long long x=(x1-x2)*(x1-x2), y=(y1-y2)*(y1-y2); \n        return x+y<=r*r; //using the distance formula\n    }\n    \n    void help(vector<vector<int>>& bombs,vector<bool>& vis,int j, int& count){\n        if(vis[j])return; //if we have already detonated this bomb \n        \n        count++;\n        vis[j]=true;\n        int x1=bombs[j][0], y1=bombs[j][1], r=bombs[j][2];\n        \n        for(int i=0;i<bombs.size();i++){\n            int x2=bombs[i][0], y2=bombs[i][1];\n            if(!vis[i] && check(x1,x2,y1,y2,r)) //check if this bomb can be detonated using the previous bomb\n            help(bombs,vis,i,count);\n        }\n    }\n    \n    int maximumDetonation(vector<vector<int>>& bombs) {\n        int n=bombs.size();\n        int ans=INT_MIN;\n        \n        for(int i=0;i<n;i++){\n            int count=0; \n            vector<bool>visited(n,false);  // a visted array to keep track of the bombs already reached in the current sequence\n            help(bombs,visited,i,count);\n            ans=max(ans,count);\n        }\n        return ans;\n    }\n};\n```
['Depth-First Search', 'C++']