蓝桥杯2022年第十三届省赛真题-扫雷

解题思路:

暴力的将排雷火箭和爆炸的地雷装入队列对余下的地雷进行检验是否能引爆

我使用了一点小优化,在装地雷的数组中,将引爆的地雷放到数组的前面,下次遍历地雷数组时就可以只遍历还没引爆的地雷了

注意使用较快的输入和输出
参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	long long x,y,r;
}boom[1000005];
queue<node>q;
bool check(node a,node b)
{
	return a.r*a.r>=((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&boom[i].x,&boom[i].y,&boom[i].r);
	}
	for(int i=1;i<=m;i++)
	{
		node t;
		scanf("%lld%lld%lld",&t.x,&t.y,&t.r);
		q.push(t);
	}
	int k=1;
	int ans=0;
	while(!q.empty())
	{
		node t;
		t=q.front();
		q.pop();
		for(int i=k;i<=n;i++)
		{
			if(check(t,boom[i]))
			{
			    q.push(boom[i]);
				swap(boom[k],boom[i]);//交换到最前面
				k++;//下次遍历就可以跳过爆炸的地雷
				ans++;	
				if(ans==n)
				{
					printf("%d",ans);
	                return 0;
				}
				//cout<<t.r<<endl;
			}
		}
		
	}
	printf("%d",ans);
	return 0;
}