汽车网站建设开题报告,Wordpress禁止爬虫ip,旅游网站建设意义,wordpress有识图插件4407. 扫雷 - AcWing题库
题目描述
分析
此题目使用map等都会超时#xff0c;所以我们可以巧妙的使用哈希模拟散列表#xff0c;哈希表初始化为-1首先将地雷读入哈希表#xff0c;找到地雷的坐标在哈希表中对应的下标#xff0c;如果没有则此地雷的位置第一次出现#…4407. 扫雷 - AcWing题库
题目描述
分析
此题目使用map等都会超时所以我们可以巧妙的使用哈希模拟散列表哈希表初始化为-1首先将地雷读入哈希表找到地雷的坐标在哈希表中对应的下标如果没有则此地雷的位置第一次出现将其存入哈希表di[key]表示哈希数组中key对应的地雷下标在这些相同位置的地雷中取最大的半径因为最大的半径炸的范围更多
枚举导弹如果有地雷且没有被访问过而且其在爆炸范围之内就可以将其进行bfs
最后遍历每个地雷看是否被标记被标记就算答案
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int X 1e9 1, M 1e6 7, N 5e4 10;
struct node
{int x, y, r;
}b[N];
ll h[M], id[M], res, n, m;
bool st[N];
ll get_he(int x, int y)//得到每个坐标的哈希值
{return (ll)x * X y;
}
int find(int x, int y)//找到坐标被哈希数组储存的下标
{ll he get_he(x, y);int key (he % M M) % M;//映射哈希数组内 while(h[key] ! -1 h[key] ! he){key ;if(key M)key 0;}return key;
}
bool check(int x, int y,int r, int xx, int yy)//判断是否在爆炸范围内
{int d (x - xx) * (x - xx) (y - yy) * (y - yy);return d r * r;
}
void bfs(int pos)
{queueintq;q.push(pos);st[pos] true;while(!q.empty()){int t q.front();q.pop();int x b[t].x, y b[t].y, r b[t].r;for(int xx x - r; xx x r; xx ){for(int yy y - r; yy y r; yy ){int key find(xx, yy);//是地雷没有访问过能炸到 if(id[key] !st[id[key]] check(x, y, r, xx, yy)){int pos id[key];st[pos] true;q.push(pos);}}}}
}
int main()
{cin n m;memset(h, -1, sizeof h);int x, y, r;for(int i 1; i n; i )//地雷 {cin x y r;b[i] {x, y, r};int key find(x, y);//找到此地雷对应的下标 if(h[key] -1)h[key] get_he(x, y);//如果此下标没有出现过就加入 if(!id[key] || b[id[key]].r r){id[key] i;}}for(int i 1; i m; i )//排雷导弹{cin x y r;for(int xx x - r; xx x r; xx )//在r的范围内但可以以圆外的方形区域作为边界 {for(int yy y - r; yy y r; yy ){int key find(xx, yy);if(id[key] !st[id[key]] check(x, y, r, xx, yy))bfs(id[key]);}} } for(int i 1; i n; i ){int key find(b[i].x, b[i].y);int pos id[key];if(pos st[pos])res ;}cout res;return 0;
}
