Detonate the most bombs - C language DFS recursive approach

The most detonated bombs

Here's a list of bombs . A bomb Explosion range Defined as a circle centered on a bomb .

The bomb uses a subscript from 0 Start with a two-dimensional integer array bombs Express , among bombs[i] = [xi, yi, ri] .xi and yi It means the first one i A bomb X and Y coordinate ,ri Indicates the explosion range radius .

You need to choose to detonate One bomb . When the bomb was detonated , all All bombs within its explosion range will be detonated , These bombs will further detonate other bombs within their explosion range .

Here's your array bombs , Please return to detonate One Under the premise of the bomb , most The number of bombs that can detonate .

Input ：bombs = [[2,1,3],[6,1,4]]
Output ：2
explain ：
The picture above shows 2 The location and explosion range of a bomb .
If we detonate the bomb on the left , The bomb on the right will not be affected .
But if we detonate the bomb on the right , Both bombs will explode .
So the maximum number of bombs that can detonate is max(1, 2) = 2 .

Input ：bombs = [[1,1,5],[10,10,5]]
Output ：1
explain ：
Detonating any bomb will not detonate another bomb . So the maximum number of bombs that can detonate is 1 .

Input ：bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
Output ：5
explain ：
The best detonating bomb is a bomb 0 , because ：

• bomb 0 Set off the bomb 1 and 2 . The red circle indicates the bomb 0 The explosion range .
• bomb 2 Set off the bomb 3 . The blue circle indicates the bomb 2 The explosion range .
• bomb 3 Set off the bomb 4 . A green circle indicates a bomb 3 The explosion range .
  So there are 5 A bomb was detonated .
  The code implementation is as follows ：

int  dfs(int** bombs, int bombsSize,int x,int y,int r,int *a,int index){
    
    int i,j;
    int n=0;
    float pi=3.1415926;
    
    int x1,y1;
  // printf("index %d ",index);
    a[index]=1;
    for(i=0;i<bombsSize;i++){
    
       

        if(i!=index&&a[i]==0){
    
        x1=bombs[i][0];
        y1=bombs[i][1]; 
       long long d1=x1-x,d2=y-y1;

     // printf("d1,d2 %d %d ",d1,d2);
        long long  d3=d1*d1+d2*d2;
        double d=d3;
        d=sqrt(d);
      // printf(" d %f ",d);

      
        if(d<=r){
    
            a[i]=1;
            n++;
            n=n+dfs(bombs,bombsSize,x1,y1,bombs[i][2],a,i);
            }
        }
     
      
    }


return n;
}


int maximumDetonation(int** bombs, int bombsSize, int* bombsColSize){
    
    int a[bombsSize];
    int i,j;
    int rz[bombsSize];
   // if(bombsSize>90) return 10;

    for(j=0;j<bombsSize;j++){
    
         for(i=0;i<bombsSize;i++){
    
               a[i]=0;
         }
         rz[j]=dfs(bombs,bombsSize,bombs[j][0],bombs[j][1],bombs[j][2],a,j)+1;

    }
    int max=rz[0];
     for(j=1;j<bombsSize;j++){
    
      if(rz[j]>max){
    
          max=rz[j];
      }

    }
    return max;

   
  
    


}