4407. 扫雷 – AcWing题库
题目描述
分析
此题目使用map等都会超时，所以我们可以巧妙的使用哈希模拟散列表，哈希表初始化为-1首先将地雷读入哈希表，找到地雷的坐标在哈希表中对应的下标，如果没有则此地雷的位置第一次出现，将其存入哈希表，di[key]表示哈希数组中key对应的地雷下标，在这些相同位置的地雷中取最大的半径，因为最大的半径炸的范围更多
枚举导弹，如果有地雷，且没有被访问过而且其在爆炸范围之内就可以将其进行bfs
最后遍历每个地雷看是否被标记，被标记就算答案
#includeusing 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){queueq;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 > n >> m;memset(h, -1, sizeof h);int x, y, r;for(int i = 1; i > 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 > 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;}