传送门
根据a炸弹能否引爆b炸弹建图
若能a->b
其中能否引爆的判断条件为ab圆心距离小于等于a的爆炸半径
然后dfs每一个节点
class Solution {
public:
int n;
int g[210][210];
bool st[210];
int dfs(int u){//求u能到的点数
st[u]=1;
int sum=0;
for (int i=0;i<n;i++){
if (g[u][i]&&!st[i]){
sum+=dfs(i)+1;
}
}
return sum;
}
int maximumDetonation(vector<vector<int>>& bom) {
n=bom.size();
int mxa=-1e9;
for (int i=0;i<n;i++){//建图 i->j
for (int j=0;j<n;j++){
if (i==j) continue;
int x1=bom[i][0],y1=bom[i][1];
int x2=bom[j][0],y2=bom[j][1];
int r1=bom[i][2],r2=bom[j][2];
double d=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
if (d<=r1){
g[i][j]=1;
}
}
}
for (int i=0;i<n;i++){
memset(st,0,sizeof st);
mxa=max(mxa,dfs(i)+1);
}
return mxa;
}
};
我递归模拟做的
我拿宽搜做的