4407. 扫雷 – AcWing题库
题目描述
分析
此题目使用map等都会超时,所以我们可以巧妙的使用哈希模拟散列表,哈希表初始化为-1首先将地雷读入哈希表,找到地雷的坐标在哈希表中对应的下标,如果没有则此地雷的位置第一次出现,将其存入哈希表,di[key]表示哈希数组中key对应的地雷下标,在这些相同位置的地雷中取最大的半径,因为最大的半径炸的范围更多
枚举导弹,如果有地雷,且没有被访问过而且其在爆炸范围之内就可以将其进行bfs
最后遍历每个地雷看是否被标记,被标记就算答案
#include
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 q;
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 > 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[ke服务器托管网y] = get_he(x, y);//如果此下标没有出现过就加入
if(!id[key] || b[id[key]].r > x >> y >> r;
for(int xx = x - r; xx
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
我是卢松松,点点上面的头像,欢迎关注我哦! 昨天出了一条新闻,意思是说:仅0.4%主播月收入超10万。这个“仅”字用的好啊! 要知道,月入1万其实已经超过了全国95%的人了,月入10万就已经超过全国99.99%的人了。只是这些短视频平台把这些收入都放大了,认为…