当前位置：网站首页>蓝桥杯2022初赛——扫雷
蓝桥杯2022初赛——扫雷
2022-06-29 02:46:00 【疯疯癫癫才自由】
4407. 扫雷
小明最近迷上了一款名为《扫雷》的游戏。
其中有一个关卡的任务如下：
在一个二维平面上放置着 n
个炸雷，第 i 个炸雷 (xi,yi,ri) 表示在坐标 (xi,yi) 处存在一个炸雷，它的爆炸范围是以半径为 ri
的一个圆。
为了顺利通过这片土地，需要玩家进行排雷。
玩家可以发射 m
个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (xj,yj,rj) 表示这个排雷火箭将会在 (xj,yj) 处爆炸，它的爆炸范围是以半径为 rj
的一个圆，在其爆炸范围内的炸雷会被引爆。
同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。
现在小明想知道他这次共引爆了几颗炸雷？
你可以把炸雷和排雷火箭都视为平面上的一个点。
一个点处可以存在多个炸雷和排雷火箭。
当炸雷位于爆炸范围的边界上时也会被引爆。
输入格式
输入的第一行包含两个整数 n、m
。
接下来的 n
行，每行三个整数 xi,yi,ri
，表示一个炸雷的信息。
再接下来的 m
行，每行三个整数 xj,yj,rj
，表示一个排雷火箭的信息。
输出格式
输出一个整数表示答案。
数据范围
对于 40%
的评测用例：0≤x,y≤109,0≤n,m≤103,1≤r≤10，
对于 100% 的评测用例：0≤x,y≤109,0≤n,m≤5×104,1≤r≤10
。
输入样例：
2 1
2 2 4
4 4 2
0 0 5
输出样例：
2
样例解释
示例图如下，排雷火箭 1
覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆盖了炸雷 2，所以炸雷 2
也被排除。
排雷火箭可以排掉地雷，地雷又可以排掉它能排掉范围内的地雷，所以显然是图的遍历问题。
可是，如果不对原始数据进行处理，直接用邻接表或者临界矩阵来建图，明显会超时。因为点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9。但是先把坐标按x轴从小到大排序，再按y轴从小到大排序，时间复杂度是O(nlgn),再加上建图的时间复杂度O(n*r),查询的时间复杂度O(m*lgn+n)。可以AC。
这道题我花了数日，研究了数种方法，有map解决，unordered_map解决，有手写hash表解决，能AC的BFS和DFS我都写出来了，不是y总讲的方法，便是在acwing上看到大佬写的代码，自己动手写了一遍。不言而喻，效率比较：手写hash > unordered_map > map,
不过话说回来，在这道题中让我学到的知识蛮不少的。
代码中我有一些调试的代码，我没删除，那一部分到也没必要看，我都注释掉了的。
一共十一种代码，能AC的倒没几种，不过在写的过程中，是满满的收获啊。学到了如何手写hash表，map和unorded_map的效率差别，知道了当自己写的结构体或者pair作为unordered_map的key值的时候，需要自己写一个函数来对他们排序，因为编译器无法知道他们的关系。当然这个函数要用类来封装。想必以后也能用上lower_bound()和upper_bound了吧。虽然都知道这些函数，但是不知道什么时候用，还是自己写的题目太少了。同志，革命尚未成功，吾得急需努力。
其实算法笔记讲解BFS的时候就已经强调了inq表示结点是否入队，而不是是否访问，否则就会存在多个点进行入队，这和DFS的vis数组是有区别的，当时还不以为然，觉得自己都理解了，现在想想，亦是惭愧！书你倒是看了，但你是否真正的吸收了呢？每学到一个算法，就要去找相应的题目来做，不然你也只是白白浪费时间，多了不说，算法笔记上的树状数组以及lowbit数组你现在是否还能知道它们的意思，KMP算法是否还有印象，快速排序是否还能写出来，组合数的知识还知道多少。。。等等，不光是低头做题，还得总结自己学到的东西，以后遇到能够用自己学过的算法解决的题目的时候，别两眼一蹬，我不会，毫无思路？那就从此处开始，把之前写的算法发成博客吧，也能再温习一遍。
万丈高楼平地起，莫在浮沙筑高台！
第一种，图的深度优先遍历，邻接表实现， 由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9， 明显会超时。
/**
图的深度优先遍历，邻接表实现
由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
明显会超时
*/
/**
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=1010;
struct Node
{
int x,y,r;
}cir[maxn];
vector<int> adj[maxn];
bool vis[maxn]={false};
int n,m;
int dfs_Trave(int x,int y,int r);
int dfs(int index);
void add(int index);
int main()
{
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=0;i<n;++i)
{
scanf("%d%d%d",&x,&y,&r);
cir[i]={x,y,r};
}
for(int i=0;i<n;++i)
{
add(i);
}
// cout << "调试:\n";
// for(int i=0;i<n;++i)
// {
// for(auto b:adj[i])
// cout << b << ' ';
// cout << endl;
// }
// cout << "jk\n";
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
// cout << "r:" << r << endl;
//printf("r:%d\n",r);
res+=dfs_Trave(x,y,r);
}
printf("%d\n",res);
return 0;
}
void add(int index)
{
for(int i=0;i<n;++i)
if(i!=index)
{
if(cir[index].r>(sqrt(pow(cir[i].x-cir[index].x,2)+pow(cir[i].y-cir[index].y,2))))
adj[index].push_back(i);
}
}
int dfs(int index)
{
//cout << "jinbulai?\n";
int sum=1;
vis[index]=true;
for(int i=0;i<adj[index].size();++i)
{
int v=adj[index][i];
if(vis[v]==false)
sum+=dfs(v);
}
return sum;
}
int dfs_Trave(int x,int y,int r)
{
// cout << "r:" << r << endl;
int sum=0;
for(int i=0;i<n;++i)
{
double L=sqrt(pow(x-cir[i].x,2)+pow(y-cir[i].y,2));
// cout << "length:" << L << endl;
if(r>L)
{
// cout << "error: \n";
if(vis[i]==false)
sum+=dfs(i);
}
}
return sum;
}第二种， 图的深度优先遍历，邻接表实现，由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，先把坐标按x轴从小到大排序，再按y轴从小到大排序， acwing 最后一组数据通不过，最开始的时候始终找不出原因，现在想想，也能理解，
当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
不然建图的时候有O(n^2)的时间复杂度。
下一个代码我给出了AC的代码；
*/
/**
图的深度优先遍历，邻接表实现
由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
先把坐标按x轴从小到大排序，再按y轴从小到大排序
acwing 最后一组数据通不过，最开始的时候始终找不出原因，现在想想，也能理解，
当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
不然建图的时候有O(n^2)的时间复杂度。
下一个代码我给出了AC的代码；
*/
/**
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
const int maxn=50010;
struct Node
{
int x,y,r;
int cnt;
Node (int _x,int _y) : x(_x),y(_y){}
Node (int _x,int _y,int _r) : x(_x),y(_y),r(_r){}
Node (int _x,int _y,int _r,int _cnt) :x(_x),y(_y),r(_r),cnt(_cnt){}
Node()=default;
bool operator < (Node const & a) const
{
if(x!=a.x)
return x<a.x;
return y<a.y;
}
}cir[maxn];
struct comp
{
int operator()(const std::pair<int, int>& p) const {
return p.first ^ p.second; //返回值为bool，比较符为&，|都比这一个慢，
}
};
typedef long long LL;
LL squ(int x)
{
return (LL) x*x;
}
vector<int> adj[maxn];
unordered_map<pair<int,int> ,int,comp> ump;
bool vis[maxn]={false};
int n,m;
int dfs_Trave(int x,int y,int r);
int dfs(int index);
void add(int index);
int main()
{
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=1;i<=n;++i)
{
scanf("%d%d%d",&x,&y,&r);
auto temp=ump[{x,y}];
if(temp!=0)
{
cir[temp].r=max(cir[temp].r,r);
cir[temp].cnt++;
}
else
{
cir[i]={x,y,r,1}; //应当用一个全局变量来表示不重复点的下标
ump[{x,y}]=i; //
}
}
sort(cir+1,cir+n+1);
// Node temp={2,3,9};
// auto it=lower_bound(cir+1,cir+n+1,temp);
// cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
// Node temp2={2,50,9};
// it=lower_bound(cir+1,cir+n+1,temp2);
// cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
// cout << "调试:\n";
// for(int i=1;i<=n;++i)
// cout << cir[i].x << ' ' << cir[i].y << ' ' << cir[i].r << endl;
// cout << "ok\n";
for(int i=1;i<=n;++i)
{
add(i);
}
// cout << "调试:\n";
// for(int i=0;i<n;++i)
// {
// for(auto b:adj[i])
// cout << b << ' ';
// cout << endl;
// }
// cout << "jk\n";
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
// cout << "r:" << r << endl;
//printf("r:%d\n",r);
res+=dfs_Trave(x,y,r);
}
printf("%d\n",res);
return 0;
}
void add(int index)
{
for(int i=index-1;i>0;--i)
{
if(squ(cir[index].r)<squ(cir[i].x-cir[index].x))
break;
if(squ(cir[index].r)>=squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
adj[index].push_back(i);
}
for(int i=index+1;i<=n;++i)
{
if(squ(cir[index].r) < squ(cir[i].x-cir[index].x))
break;
if(squ(cir[index].r) >= squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
adj[index].push_back(i);
}
}
int dfs(int index)
{
int sum=cir[index].cnt;
vis[index]=1;
for(int i=0;i<adj[index].size();++i)
{
int v=adj[index][i];
if(vis[v]==0)
sum+=dfs(v);
}
return sum;
}
int dfs_Trave(int x,int y,int r)
{
Node e1={x-r,y,r},e2={x+r,y,r};
int l=lower_bound(cir+1,cir+n+1,e1)-cir;
int ri=lower_bound(cir+1,cir+n+1,e2)-cir;
l=min(l,n),ri=min(ri,n);
int sum=0;
for(int i=l;i<=ri;++i)
{
if(i==0)
continue;
if((squ(r)>=squ(cir[i].x-x)+squ(cir[i].y-y))&&vis[i]==0)
sum+=dfs(i);
}
return sum;
}第三个，/**
图的深度优先遍历，邻接表实现
由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
先把坐标按x轴从小到大排序，再按y轴从小到大排序
当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
不然建图的时候有O(n^2)的时间复杂度。
能AC
/**
图的深度优先遍历，邻接表实现
由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
先把坐标按x轴从小到大排序，再按y轴从小到大排序
当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
不然建图的时候有O(n^2)的时间复杂度。
能AC
*/
/**
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
const int maxn=50010;
struct Node
{
int x,y,r;
int cnt;
Node (int _x,int _y) : x(_x),y(_y){}
Node (int _x,int _y,int _r) : x(_x),y(_y),r(_r){}
Node (int _x,int _y,int _r,int _cnt) :x(_x),y(_y),r(_r),cnt(_cnt){}
Node()=default;
bool operator < (Node const & a) const
{
if(x!=a.x)
return x<a.x;
return y<a.y;
}
}cir[maxn];
struct comp
{
int operator()(const std::pair<int, int>& p) const {
return p.first ^ p.second; //返回值为bool，比较符为&，|都比这一个慢，
}
};
typedef long long LL;
LL squ(int x)
{
return (LL) x*x;
}
vector<int> adj[maxn];
unordered_map<pair<int,int> ,int,comp> ump; //实践上机证明将坐标转化为long long 比这种方式快上一点
bool vis[maxn]={false};
int n,m,n1=0;
int dfs_Trave(int x,int y,int r);
int dfs(int index);
void add(int index);
int main()
{
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=1;i<=n;++i)
{
scanf("%d%d%d",&x,&y,&r);
auto temp=ump[{x,y}];
if(temp!=0)
{
cir[temp].r=max(cir[temp].r,r);
cir[temp].cnt++;
}
else
{
cir[++n1]={x,y,r,1};
ump[{x,y}]=n1;
// cir[i].cnt=1;
}
}
sort(cir+1,cir+n1+1);
// Node temp={2,3,9};
// auto it=lower_bound(cir+1,cir+n+1,temp);
// cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
// Node temp2={2,50,9};
// it=lower_bound(cir+1,cir+n+1,temp2);
// cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
// cout << "调试:\n";
// for(int i=1;i<=n;++i)
// cout << cir[i].x << ' ' << cir[i].y << ' ' << cir[i].r << endl;
// cout << "ok\n";
for(int i=1;i<=n1;++i)
{
add(i);
}
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
res+=dfs_Trave(x,y,r);
}
printf("%d\n",res);
return 0;
}
void add(int index)
{
for(int i=index-1;i>0;--i)
{
if(squ(cir[index].r)<squ(cir[i].x-cir[index].x))
break;
if(squ(cir[index].r)>=squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
adj[index].push_back(i);
}
for(int i=index+1;i<=n1;++i)
{
if(squ(cir[index].r) < squ(cir[i].x-cir[index].x))
break;
if(squ(cir[index].r) >= squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
adj[index].push_back(i);
}
}
int dfs(int index)
{
int sum=cir[index].cnt;
vis[index]=1;
for(int i=0;i<adj[index].size();++i)
{
int v=adj[index][i];
if(vis[v]==0)
sum+=dfs(v);
}
return sum;
}
int dfs_Trave(int x,int y,int r)
{
Node e1={x-r,y,r},e2={x+r,y,r};
int l=lower_bound(cir+1,cir+n1+1,e1)-cir;
int ri=lower_bound(cir+1,cir+n1+1,e2)-cir;
l=min(l,n1),ri=min(ri,n1);
int sum=0;
for(int i=l;i<=ri;++i)
{
if(i==0)
continue;
if((squ(r)>=squ(cir[i].x-x)+squ(cir[i].y-y))&&vis[i]==0)
sum+=dfs(i);
}
return sum;
}第四个， 图的广度优先遍历，邻接表实现
由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
先把坐标按x轴从小到大排序，再按y轴从小到大排序
当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
不然建图的时候有O(n^2)的时间复杂度。
能AC
/**
图的广度优先遍历，邻接表实现
由于点数有1e5,那么遍历所有图上的点是否联通，需要O(n^2)也就是需要2.5e9，
先把坐标按x轴从小到大排序，再按y轴从小到大排序
当许多坐标扎堆在同一点的时候，应当去掉重复的点，只留下半径最大的点。
不然建图的时候有O(n^2)的时间复杂度。
能AC
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
const int maxn=50010;
struct Node
{
int x,y,r;
int cnt;
Node (int _x,int _y) : x(_x),y(_y){}
Node (int _x,int _y,int _r) : x(_x),y(_y),r(_r){}
Node (int _x,int _y,int _r,int _cnt) :x(_x),y(_y),r(_r),cnt(_cnt){}
Node()=default;
bool operator < (Node const & a) const
{
if(x!=a.x)
return x<a.x;
return y<a.y;
}
}cir[maxn];
struct comp
{
int operator()(const std::pair<int, int>& p) const {
return p.first ^ p.second; //返回值为bool，比较符为&，|都比这一个慢，
}
};
typedef long long LL;
LL squ(int x)
{
return (LL) x*x;
}
vector<int> adj[maxn];
unordered_map<pair<int,int> ,int,comp> ump; //实践上机证明将坐标转化为long long 比这种方式快上一点
bool vis[maxn]={false};
int n,m,n1=0;
int bfs_Trave(int x,int y,int r);
int bfs(int index);
void add(int index);
int main()
{
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=1;i<=n;++i)
{
scanf("%d%d%d",&x,&y,&r);
auto temp=ump[{x,y}];
if(temp!=0)
{
cir[temp].r=max(cir[temp].r,r);
cir[temp].cnt++;
}
else
{
cir[++n1]={x,y,r,1};
ump[{x,y}]=n1;
// cir[i].cnt=1;
}
}
sort(cir+1,cir+n1+1);
// Node temp={2,3,9};
// auto it=lower_bound(cir+1,cir+n+1,temp);
// cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
// Node temp2={2,50,9};
// it=lower_bound(cir+1,cir+n+1,temp2);
// cout << "tiaoshi: " << it->x << ' ' << it->y << ' ' << it->r << endl;
// cout << "调试:\n";
// for(int i=1;i<=n;++i)
// cout << cir[i].x << ' ' << cir[i].y << ' ' << cir[i].r << endl;
// cout << "ok\n";
for(int i=1;i<=n1;++i)
{
add(i);
}
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
res+=bfs_Trave(x,y,r);
}
printf("%d\n",res);
return 0;
}
void add(int index)
{
for(int i=index-1;i>0;--i)
{
if(squ(cir[index].r)<squ(cir[i].x-cir[index].x))
break;
if(squ(cir[index].r)>=squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
adj[index].push_back(i);
}
for(int i=index+1;i<=n1;++i)
{
if(squ(cir[index].r) < squ(cir[i].x-cir[index].x))
break;
if(squ(cir[index].r) >= squ(cir[i].x-cir[index].x)+squ(cir[i].y-cir[index].y))
adj[index].push_back(i);
}
}
int bfs(int index)
{
queue<int> q;
q.push(index);
int sum=cir[index].cnt;
while(!q.empty())
{
int top=q.front();
q.pop();
for(int i=0;i<adj[top].size();++i)
{
int v=adj[top][i];
if(vis[v]==0)
{
vis[v]=1;
sum+=cir[v].cnt;
q.push(v);
}
}
}
return sum;
}
int bfs_Trave(int x,int y,int r)
{
Node e1={x-r,y,r},e2={x+r,y,r};
int l=lower_bound(cir+1,cir+n1+1,e1)-cir;
int ri=lower_bound(cir+1,cir+n1+1,e2)-cir;
l=min(l,n1),ri=min(ri,n1);
int sum=0;
for(int i=l;i<=ri;++i)
{
if(i==0)
continue;
if((squ(r)>=squ(cir[i].x-x)+squ(cir[i].y-y))&&vis[i]==0)
{
vis[i]=1;
sum+=bfs(i);
}
}
return sum;
}第五个，/**
map，将坐标用pair<int,int>存在map中
*/
/**
1)每输入一个排雷火箭，就算出它排掉了多少雷，但是由于一个位置有多个雷
，所以要把这个位置的地雷数给记录下来；
acwing通过5/11
*/
/**
map，将坐标用pair<int,int>存在map中
*/
/**
1)每输入一个排雷火箭，就算出它排掉了多少雷，但是由于一个位置有多个雷
，所以要把这个位置的地雷数给记录下来；
acwing通过5/11
*/
/**
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
LL squ(int x)
{
return (LL) x*x;
}
map<pair<int,int>,pair<int,int> > mp;
map<pair<int,int>,int > vis;
int n,m;
int dfs_Trave(int x,int y,int r);
int dfs(pair<pair<int,int>,pair<int,int> > index);
int main()
{
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=0;i<n;++i)
{
scanf("%d%d%d",&x,&y,&r);
auto temp=make_pair(x,y);
auto it=mp.find(temp);
if(it==mp.end())
{
vis[temp]=0;
auto val=make_pair(r,1);
mp[temp]=val;
}
else
{
if(r>it->second.first)
{
auto val=make_pair(r,it->second.second+1);
mp[temp]=val;
}
else
{
auto val=make_pair(it->second.first,it->second.second+1);
mp[temp]=val;
}
}
}
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
res+=dfs_Trave(x,y,r);
}
printf("%d\n",res);
return 0;
}
int dfs(pair<pair<int,int>,pair<int,int> > index)
{
int x=index.first.first,y=index.first.second,r=index.second.first,num=index.second.second;
int sum=num;
//cout << "调试:" << sum << endl;
vis[index.first]=1;
for(int l=x-r;l<=x+r;++l)
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
auto temp=make_pair(l,s);
auto it=mp.find(temp);
if(it!=mp.end())
{
if(vis[temp]==0)
sum+=dfs(*it);
}
}
}
return sum;
}
int dfs_Trave(int x,int y,int r)
{
int sum=0;
for(int l=x-r;l<=x+r;++l)
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
auto temp=make_pair(l,s);
auto it=mp.find(temp);
if(it!=mp.end())
{
if(vis[temp]==0)
sum+=dfs(*it);
}
}
}
return sum;
}
*/
第六个，/**
2)先把排掉的雷给记录下来，最后统一计算，只记录半径，不用记录每个位置有多少雷；
当相应的就需要把所有的地雷的位置给记录下来，即使他们是相同的位置这就是cir数组的作用
acwing也是通过5/11
*/
/**
2)先把排掉的雷给记录下来，最后统一计算，只记录半径，不用记录每个位置有多少雷；
当相应的就需要把所有的地雷的位置给记录下来，即使他们是相同的位置这就是cir数组的作用
acwing也是通过5/11
*/
/**
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
typedef long long LL;
LL squ(int x)
{
return (LL) x*x;
}
const int maxn=50010;
struct Node
{
int x,y,r;
}cir[maxn];
map<pair<int,int>,int > mp;
map<pair<int,int>,int > vis;
int n,m;
void dfs_Trave(int x,int y,int r);
void dfs(pair<pair<int,int>,int > index);
int main()
{
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=0;i<n;++i)
{
scanf("%d%d%d",&x,&y,&r);
cir[i]={x,y,r};
auto temp=make_pair(x,y);
auto it=mp.find(temp);
if(it==mp.end())
{
vis[temp]=0;
mp[temp]=r;
}
else
{
if(r>it->second)
mp[temp]=r;
}
}
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
dfs_Trave(x,y,r);
}
for(int i=0;i<n;++i)
{
auto temp=make_pair(cir[i].x,cir[i].y);
if(vis[temp]!=0)
++res;
}
printf("%d\n",res);
return 0;
}
void dfs(pair<pair<int,int>,int > index)
{
int x=index.first.first,y=index.first.second,r=index.second;
vis[index.first]=1;
for(int l=x-r;l<=x+r;++l)
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
auto temp=make_pair(l,s);
auto it=mp.find(temp);
if(it!=mp.end())
{
if(vis[temp]==0)
dfs(*it);
}
}
}
}
void dfs_Trave(int x,int y,int r)
{
for(int l=x-r;l<=x+r;++l)
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
auto temp=make_pair(l,s);
auto it=mp.find(temp);
if(it!=mp.end())
{
if(vis[temp]==0)
dfs(*it);
}
}
}
}
*/第七个，/**
unorder_map解决，将坐标用pair<int,int>存在unordered_map中
*/
/**
1)对于没有默认的哈希函数的类型，如自定义的 class 类型，pair 类型等，我们就必须自己
指定一个哈希函数。这也是为什么直接构建 pair 类型的 unordered_set
如 unordered_set<pair<int, int>> uset 会出现问题
acwing通过5/11
*/
/**
unorder_map解决，将坐标用pair<int,int>存在unordered_map中
*/
/**
1)对于没有默认的哈希函数的类型，如自定义的 class 类型，pair 类型等，我们就必须自己
指定一个哈希函数。这也是为什么直接构建 pair 类型的 unordered_set
如 unordered_set<pair<int, int>> uset 会出现问题
acwing通过5/11
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <unordered_map>
using namespace std;
typedef long long LL;
LL squ(int x)
{
return (LL) x*x;
}
const int maxn=50010;
/*
struct cmp
{
bool operator()(pair<int,int> const &p) const
{
return p.first<p.second;
}
};
*/
//struct cmp
//{
// std::size_t operator()(const std::pair<int, int>& p) const {
// return p.first ^ p.second;
// }
//};
struct cmp
{
int operator()(const std::pair<int, int>& p) const {
return p.first ^ p.second; //返回值为bool，比较符为&，|都比这一个慢，
}
};
struct Node
{
int x,y,r;
}cir[maxn];
unordered_map<pair<int,int>,int ,cmp> mp;
unordered_map<pair<int,int>,int ,cmp> vis;
int n,m;
void dfs_Trave(int x,int y,int r);
void dfs(pair<pair<int,int>,int > index);
int main()
{
// int a=123456789,b=123456;
// int c=a&b;
// cout << c << endl;
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=0;i<n;++i)
{
scanf("%d%d%d",&x,&y,&r);
cir[i]={x,y,r};
auto temp=make_pair(x,y);
auto it=mp.find(temp);
if(it==mp.end())
{
vis[temp]=0;
mp[temp]=r;
}
else
{
if(r>it->second)
mp[temp]=r;
}
}
/*
cout << "调试:\n";
for(auto val:mp)
cout << val.first.first << ' ' << val.first.second << ' ' << val.second << endl;
*/
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
dfs_Trave(x,y,r);
}
for(int i=0;i<n;++i)
{
auto temp=make_pair(cir[i].x,cir[i].y);
if(vis[temp]!=0)
++res;
}
printf("%d\n",res);
return 0;
}
void dfs(pair<pair<int,int>,int > index)
{
int x=index.first.first,y=index.first.second,r=index.second;
vis[index.first]=1;
for(int l=x-r;l<=x+r;++l)
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
auto temp=make_pair(l,s);
auto it=mp.find(temp);
if(it!=mp.end())
{
if(vis[temp]==0)
dfs(*it);
}
}
}
}
void dfs_Trave(int x,int y,int r)
{
for(int l=x-r;l<=x+r;++l)
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
auto temp=make_pair(l,s);
auto it=mp.find(temp);
if(it!=mp.end())
{
if(vis[temp]==0)
dfs(*it);
}
}
}
}第八个，/**
将坐标转换为一个long long数值，存在unorder_map中；
acwing通过了6/11；
*/
/**
将坐标转换为一个long long数值，存在unorder_map中；
acwing通过了6/11；
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
typedef long long LL;
LL squ(int x)
{
return (LL) x*x;
}
const int maxn=50010,inf=1e9;
LL hash_val(int x,int y)
{
return x*(inf+1ll)+y;
}
/*
struct cmp
{
bool operator()(pair<int,int> const &p) const
{
return p.first<p.second;
}
};
*/
//struct cmp
//{
// std::size_t operator()(const std::pair<int, int>& p) const {
// return p.first ^ p.second;
// }
//};
//struct cmp
//{
// int operator()(const LL, int>& p) const {
// return p.first < p.second;
// }
//};
//struct Node
//{
// int x,y,r;
//}cir[maxn];
vector<LL> cir;
unordered_map<LL,int> mp;
unordered_map<LL,int> vis;
int n,m;
void dfs_Trave(int x,int y,int r);
void dfs(int x,int y,int r);
int main()
{
// int a=123456789,b=123456;
// int c=a&b;
// cout << c << endl;
// int a=123456789,b=45612;
// cout << hash_val(a,b) << endl;
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=0;i<n;++i)
{
scanf("%d%d%d",&x,&y,&r);
//cir[i]={x,y,r};
LL temp=hash_val(x,y);
//string temp=to_string(val);
cir.push_back(temp);
// mp[temp]=r;
// vis[temp]=0;
auto it=mp.find(temp);
if(it==mp.end())
{
vis[temp]=0;
mp[temp]=r;
}
else
{
if(r>it->second)
mp[temp]=r;
}
}
// cout << "调试:\n";
// for(auto val:mp)
// cout << val.first << ' ' << val.second << endl;
// cout << "\ntiaoshi\n";
// for(auto a:vis)
// cout << a.first << ' ' << a.second << endl;
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
dfs_Trave(x,y,r);
}
// cout << "\ntiaoshi2:\n";
// for(auto a:vis)
// cout << a.first << ' ' << a.second << endl;
for(int i=0;i<n;++i)
{
auto temp=cir[i];
if(vis[temp]!=0)
++res;
}
printf("%d\n",res);
return 0;
}
void dfs(int x,int y,int r)
{
LL val=hash_val(x,y);
// int x=index.first.first,y=index.first.second,r=index.second;
vis[val]=1;
for(int l=x-r;l<=x+r;++l)
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
auto temp=hash_val(l,s);
auto it=mp.find(temp);
if(it!=mp.end())
{
if(vis[temp]==0)
dfs(l,s,it->second);
}
}
}
}
void dfs_Trave(int x,int y,int r)
{
for(int l=x-r;l<=x+r;++l)
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
LL temp=hash_val(l,s);
//string temp=to_string(val);
auto it=mp.find(temp);
if(it!=mp.end())
{
if(vis[temp]==0)
dfs(l,s,it->second);
}
}
}
}
第九个，
/**
将坐标转换为string，存在unordered_map中
在acwing只能过4/11；
*/
/**
将坐标转换为string，存在unordered_map中
在acwing只能过4/11；
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
typedef long long LL;
LL squ(int x)
{
return (LL) x*x;
}
const int maxn=50010,inf=1e9;
LL hash_val(int x)
{
return x*(inf+1ll);
}
/*
struct cmp
{
bool operator()(pair<int,int> const &p) const
{
return p.first<p.second;
}
};
*/
//struct cmp
//{
// std::size_t operator()(const std::pair<int, int>& p) const {
// return p.first ^ p.second;
// }
//};
//struct cmp
//{
// int operator()(const LL, int>& p) const {
// return p.first < p.second;
// }
//};
//struct Node
//{
// int x,y,r;
//}cir[maxn];
vector<string> cir;
unordered_map<string,int> mp;
unordered_map<string,int> vis;
int n,m;
void dfs_Trave(int x,int y,int r);
void dfs(int x,int y,int r);
int main()
{
// int a=123456789,b=123456;
// int c=a&b;
// cout << c << endl;
// int a=123456789,b=45612;
// cout << hash_val(a,b) << endl;
// int a=122,b=456;
// string s=to_string(a) +' ' +to_string(b);
// cout << s << endl;
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=0;i<n;++i)
{
scanf("%d%d%d",&x,&y,&r);
//cir[i]={x,y,r};
LL val=hash_val(x);
string temp=to_string(val)+' ' +to_string(y);
cir.push_back(temp);
// mp[temp]=r;
// vis[temp]=0;
auto it=mp.find(temp);
if(it==mp.end())
{
vis[temp]=0;
mp[temp]=r;
}
else
{
if(r>it->second)
mp[temp]=r;
}
}
// cout << "调试:\n";
// for(auto val:mp)
// cout << val.first << ' ' << val.second << endl;
// cout << "\ntiaoshi\n";
// for(auto a:vis)
// cout << a.first << ' ' << a.second << endl;
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
dfs_Trave(x,y,r);
}
// cout << "\ntiaoshi2:\n";
// for(auto a:vis)
// cout << a.first << ' ' << a.second << endl;
for(int i=0;i<n;++i)
{
auto temp=cir[i];
if(vis[temp]!=0)
++res;
}
printf("%d\n",res);
return 0;
}
void dfs(int x,int y,int r)
{
LL val=hash_val(x);
string temp=to_string(val) +' ' + to_string(y);
// int x=index.first.first,y=index.first.second,r=index.second;
vis[temp]=1;
for(int l=x-r;l<=x+r;++l)
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
LL val=hash_val(l);
string temp=to_string(val)+' ' +to_string(s);
auto it=mp.find(temp);
if(it!=mp.end())
{
if(vis[temp]==0)
dfs(l,s,it->second);
}
}
}
}
void dfs_Trave(int x,int y,int r)
{
for(int l=x-r;l<=x+r;++l)
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
LL val=hash_val(l);
string temp=to_string(val)+' ' + to_string(s);
auto it=mp.find(temp);
if(it!=mp.end())
{
if(vis[temp]==0)
dfs(l,s,it->second);
}
}
}
}
第十个，/**
dfs实现图的遍历
手写hash表：把每个点唯一表示一个值，然后存到一个数组中，由于最大值为1e9，
所以可以把x坐标乘以一个(1e9+1)+y的坐标表示一个long long 值，也不会溢出，
即表示为一个两位的进制数，不过这个进制是1e9+1；
能AC;
*/
/**
dfs实现图的遍历
手写hash表：把每个点唯一表示一个值，然后存到一个数组中，由于最大值为1e9，
所以可以把x坐标乘以一个(1e9+1)+y的坐标表示一个long long 值，也不会溢出，
即表示为一个两位的进制数，不过这个进制是1e9+1；
能AC;
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=1e9,mod=7000003;
int test=999997; //测试数是否为素数
typedef long long LL;
struct Node
{
int x,y,r;
}cir[mod];
LL hs[mod]={0};
int id[mod]={0},vis[mod]={0};
int m,n;
void dfs(int x,int y,int r);
void dfs_Trave(int x,int y,int r);
LL hash_val(int x,int y) //将二维坐标转换为一个hash值
{
return (maxn+1ll)*x+y;
}
int hash_key(int x,int y)
{
LL val=hash_val(x,y);
int k=1,flag=-1;
int key=(val%mod+mod)%mod;
while(hs[key]!=-1&&hs[key]!=val) //此处需要hs[key]!=key,因为后面需要查找用到二维坐标，
{ //返回一个key值
key+=k*k*flag; //由于一个坐标最开始对应的key值也许被其他坐标占用了，这就需要查找
++k; //一个没被用到的值，但考虑到一个值一个值的加，元素容易扎堆都被使用了，
flag*=-1; //于是我们就用平方探查法来查找
key=(key%mod+mod)%mod; //防止出现负值
}
return key;
}
LL squ(int x)
{
return (LL) x*x;
}
void is_primer(int n)
{
for(int i=2;i<=sqrt(n);++i)
if(n%i==0)
{
cout << " not is primer ;\n";
return;
}
cout << "is primer\n";
return;
}
int main()
{
is_primer(test);
memset(hs,-1,sizeof(hs));
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=0;i<n;++i)
{
scanf("%d%d%d",&x,&y,&r);
cir[i]={x,y,r};
auto key=hash_key(x,y);
if(hs[key]==-1) //这一个if语句需不需要都行
hs[key]=hash_val(x,y);
if(!id[key]||r>id[key]) //如果id[key]第一次被使用，或者此点的半径比之前的大，
id[key]=r; //那么更新这个点的半径
}
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
dfs_Trave(x,y,r);
}
for(int i=0;i<n;++i)
{
auto key=hash_key(cir[i].x,cir[i].y);
if(vis[key]!=0)
++res;
}
printf("%d\n",res);
return 0;
}
void dfs(int x,int y,int r)
{
int key=hash_key(x,y);
vis[key]=1;
for(int l=x-r;l<=x+r;++l) //遍历（x，y）周围可以炸到的所有点
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
int key=hash_key(l,s);
if(hs[key]!=-1) //如果这个点处有炸弹
{
if(vis[key]==0) //如果这个点处的炸弹没被拆除掉
dfs(l,s,id[key]);
}
}
}
}
void dfs_Trave(int x,int y,int r)
{
for(int l=x-r;l<=x+r;++l) //遍历（x，y）周围可以炸到的所有点
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
int key=hash_key(l,s);
if(hs[key]!=-1) //如果这个点处有炸弹
{
if(vis[key]==0) //如果这个点处的炸弹没被拆除掉
dfs(l,s,id[key]);
}
}
}
}
第十一个， 用BFS实现图的遍历，
手写hash表：把每个点唯一表示一个值，然后存到一个数组中，由于最大值为1e9，
所以可以把x坐标乘以一个(1e9+1)+y的坐标表示一个long long 值，也不会溢出，
即表示为一个两位的进制数，不过这个进制是1e9+1；
true coding，能AC
值得一提的是，vis[key]应当在进入bfs的队列便更新这个值已被访问，否则取出一个坐标的时候再更新，会导致一个点多次入队，浪费许多时间，acwing上最后一组数据超时，问题便出现在这儿
其实算法笔记讲解BFS的时候就已经强调了inq表示结点是否入队，而不是是否访问，这和DFS的vis数组是有区别的，当是还不以为然，觉得自己都理解了，现在想想，亦是惭愧！书你倒是看了，但你是否真正的吸收了呢？每学到一个算法，就要去找相应的题目来做，不然你也只是白白浪费时间，多了不说，算法笔记上的树状数组以及lowbit数组你现在是否还能知道它们的意思，KMP算法是否还有印象，快速排序是否还能写出来，组合数的知识还知道多少。。。等等，不光是低头做题，还得总结自己学到的东西，以后遇到能够用自己学过的算法解决的题目的时候，别两眼一蹬，我不会？那就从此处开始，把之前写的算法发成博客吧，也能再温习一遍。
/**
用BFS实现图的遍历，
手写hash表：把每个点唯一表示一个值，然后存到一个数组中，由于最大值为1e9，
所以可以把x坐标乘以一个(1e9+1)+y的坐标表示一个long long 值，也不会溢出，
即表示为一个两位的进制数，不过这个进制是1e9+1；
true coding，能AC
*/
/**
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=1e9,mod=700001,ne=50010;
int test=700001; //测试数是否为素数
typedef long long LL;
struct Node
{
int x,y,r;
}cir[ne];
LL hs[mod]={0};
int id[mod]={0},vis[mod]={0};
int m,n;
void bfs(Node zd);
void bfs_Trave(int x,int y,int r);
LL hash_val(int x,int y) //将二维坐标转换为一个hash值
{
return (maxn+1ll)*x+y;
}
int hash_key(int x,int y)
{
LL val=hash_val(x,y);
int k=1,flag=-1;
int key=(val%mod+mod)%mod;
while(hs[key]!=-1&&hs[key]!=val) //此处需要hs[key]!=key,因为后面需要查找用到二维坐标，
{ //返回一个key值
key+=k*k*flag; //由于一个坐标最开始对应的key值也许被其他坐标占用了，这就需要查找
++k; //一个没被用到的值，但考虑到一个值一个值的加，元素容易扎堆都被使用了，
flag*=-1; //于是我们就用平方探查法来查找
key=(key%mod+mod)%mod; //防止出现负值
}
return key;
}
LL squ(int x)
{
return (LL) x*x;
}
void is_primer(int n)
{
for(int i=2;i<=sqrt(n);++i)
if(n%i==0)
{
cout << " not is primer ;\n";
return;
}
cout << "is primer\n";
return;
}
int main()
{
//is_primer(test);
memset(hs,-1,sizeof(hs));
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=0;i<n;++i)
{
scanf("%d%d%d",&x,&y,&r);
cir[i]={x,y,r};
auto key=hash_key(x,y);
if(hs[key]==-1) //这一个if语句需不需要都行
hs[key]=hash_val(x,y);
if(!id[key]||r>id[key]) //如果id[key]第一次被使用，或者此点的半径比之前的大，
id[key]=r; //那么更新这个点的半径
}
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
bfs_Trave(x,y,r);
}
for(int i=0;i<n;++i)
{
auto key=hash_key(cir[i].x,cir[i].y);
if(vis[key]!=0)
++res;
}
printf("%d\n",res);
return 0;
}
void bfs(Node zd)
{
queue<Node> q;
q.push(zd);
while(!q.empty())
{
Node temp=q.front();
int x=temp.x,y=temp.y,r=temp.r;
q.pop();
int key=hash_key(x,y);
// vis[key]=1;
for(int l=x-r;l<=x+r;++l) //遍历（x，y）周围可以炸到的所有点
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
int key=hash_key(l,s);
if(hs[key]!=-1) //如果这个点处有炸弹
{
if(vis[key]==0) //如果这个点处的炸弹没被拆除掉
{
q.push({l,s,id[key]});
vis[key]=1; //值得一提的是，vis[key]应当在进入bfs的队列便更新这个值已被访问
} //，否则取出一个坐标的时候再更新，会导致一个点多次入队
} //，浪费许多时间，acwing上最后一组数据超时，问题便出现在这儿
}
}
}
}
void bfs_Trave(int x,int y,int r)
{
for(int l=x-r;l<=x+r;++l) //遍历（x，y）周围可以炸到的所有点
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
int key=hash_key(l,s);
if(hs[key]!=-1) //如果这个点处有炸弹
{
if(vis[key]==0) //如果这个点处的炸弹没被拆除掉
{
vis[key]=1;
bfs({l,s,id[key]});
}
}
}
}
}
*/最后一个代码，是acwing上看的，因为我写的BFS始终由一组数据通不过，便对照着他的写，但还是有一组数据通不过，根本原因还是BFS入队的时候便要更新坐标已入队，否则会造成一个点多次入队，这一点必须谨记。和上一个一个代码唯一的不同便是这个id数组记录的是cir数组的下标，也就是存储在cir数组里的下标，上一个id存储的相同点的最大半径。
/**借鉴正确代码
*/
/**
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=1e9,mod=1e6 + 7,ne=50010;
int test=700001; //测试数是否为素数
typedef long long LL;
struct Node
{
int x,y,r;
}cir[ne];
LL hs[mod]={0};
int id[mod]={0}; //id存储的是坐标在数组cir中对应的下标
bool vis[ne]={0};
int m,n;
void bfs(int index);
void bfs_Trave(int x,int y,int r);
LL hash_val(int x,int y) //将二维坐标转换为一个hash值
{
return (maxn+1ll)*x+y;
}
int hash_key(int x,int y)
{
LL val=hash_val(x,y);
int key=(val%mod+mod)%mod;
while(hs[key]!=-1&&hs[key]!=val) //此处需要hs[key]!=key,因为后面需要查找用到二维坐标，
{ //返回一个key值
key++;
if(key == mod) key = 0; //防止出现负值
}
return key;
}
LL squ(int x)
{
return (LL) x*x;
}
int main()
{
memset(hs,-1,sizeof(hs));
scanf("%d%d",&n,&m);
int x,y,r;
for(int i=1;i<=n;++i)
{
scanf("%d%d%d",&x,&y,&r);
cir[i]={x,y,r};
auto key=hash_key(x,y);
if(hs[key]==-1) //这一个if语句需不需要都行
hs[key]=hash_val(x,y);
if(!id[key]||r>cir[id[key]].r) //如果id[key]第一次被使用，或者此点的半径比之前的大，
id[key]=i; //那么更新这个点的坐标下标
}
int res=0;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&x,&y,&r);
bfs_Trave(x,y,r);
}
for(int i=1;i<=n;++i)
{
auto key=hash_key(cir[i].x,cir[i].y);
int pos=id[key];
if(pos&&vis[pos])
++res;
}
printf("%d\n",res);
return 0;
}
void bfs(int index)
{
queue<int> q;
q.push(index);
vis[index]=1;
while(!q.empty())
{
int temp=q.front();
int x=cir[temp].x,y=cir[temp].y,r=cir[temp].r;
q.pop();
//int key=hash_key(x,y);
//vis[temp]=1; //在这儿将temp号的值赋为1便是错的，不知道原因
for(int l=x-r;l<=x+r;++l) //遍历（x，y）周围可以炸到的所有点
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
int key=hash_key(l,s);
if(id[key]&&!vis[id[key]]) //如果这个点处有炸弹
{
int pos=id[key];//如果这个点处的炸弹没被拆除掉
q.push(pos);
vis[pos]=1;
}
}
}
}
}
void bfs_Trave(int x,int y,int r)
{
for(int l=x-r;l<=x+r;++l) //遍历（x，y）周围可以炸到的所有点
for(int s=y+r;s>=y-r;--s)
{
if(squ(r) >= squ(l-x) + squ(s-y))
{
int key=hash_key(l,s);
if(id[key]&&!vis[id[key]]) //如果这个点处有炸弹
{ //如果这个点处的炸弹没被拆除掉
bfs(id[key]);
}
}
}
}边栏推荐
- matlab习题 —— 图像绘制练习
- Introduction to openresty
- PWN攻防世界Level2
- leetcode 统计无向图中无法互相到达点对数
- LinkedList学习
- "The first share of endoscope" broke into IPO two times. Last year, it lost 500million yuan. The commercialization of core products is still in doubt | IPO Express
- EMC、EMI、EMS的关系
- Informatics Olympiad all in one 1361: production | Luogu P1037 [noip2002 popularization group] production
- STM32L4系列单片机ADC通过内部参考电压精确计算输入电压
- apache不解析PHP文件,直接显示源码
猜你喜欢
How to optimize databases and tables
音响是如何把微弱声音放大呢
1110: nearest common ancestor (function topic)
LabVIEW generate application (exe) and installer
LabVIEW jump to web page
leetcode 统计无向图中无法互相到达点对数
Understanding and design of high concurrency
There's a mystery behind the little login
mgalcu-a509
矩阵特征值和特征向量求解——特征值分解（EVD）
随机推荐
Today's sleep quality record 82 points
Mipi d-phy -- contents of HS and LP agreements
PWN攻防世界Level2
Equal wealth
Method overload summary
leetcode 统计放置房子的方式数
Bluetooth solution | Lenz technology Amazon direct connected magic lantern solution
thinkphp5.1 runtime文件改成777权限了, 还是无法写入
MySQL binlog log cleanup
PHP XML expat parser
centos7 安装php7.2
18. `bs对象.节点名.next_sibling` 获取兄弟节点
Informatics Olympiad 1361: Produce
[线性代数] 1.2 全排列和对换
Kubernetes: container resource requirements and constraints (constraints)
线程池是什么老鸡？
The thinkphp5.1 runtime file has been changed to 777 permission, but cannot be written
高并发的理解与设计方案
leetcode 统计无向图中无法互相到达点对数
[linear algebra] 1.2 total permutation and commutation