许健跃

用户名：Kazimierz

访问量：3254

签　名：

等　　级
排　　名	3276
经　　验	1976
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校	长江大学
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

蓝桥杯2022年第十三届省赛-统计子矩阵(前缀和暴力 and 双指针优化)
浏览：979

K-进制数(简简单单写个dfs)
浏览：120

K-进制数(排列组合解)
浏览：685

你可能喜欢

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

蓝桥杯2022年第十三届省赛-扫雷(dfs+手写哈希)--技巧总结

　　作者: 许健跃　　　　发表时间：2022-09-03 20:56:59 浏览：1849　|　评论：0　

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

## 1.技巧总结
### 1.1 n进制降维
本题地雷坐标的x，y取值范围过大($$0≤x,y≤10^9$$)，如果直接把x，y当作下标会爆数组。因此我们可以通过将二维数对{x,y}看作是一个$$10^9+1$$进制数，高位是x，低位是y，有$$(xy)_{10^9+1}=x\times(10^9+1)+y$$,于是我们便将一组二维数对{x,y}映射成了一维唯一值，从而达到了编码和降维的目的。
### 1.2 手写哈希
由于本题数据范围过大，我们如果使用STL中的`unordered_map<typename,typename>或者map<typename,typename>`在本题中都会有超时风险，于是我们便可以考虑手写哈希函数**(据说速度是map的十倍左右)**。
#### 1.2.1 哈希模板-开放寻址法（写法较为固定）
```
int find(LL x)
{
    int t = (x % M + M) % M;
    while(hash1[t]!=-1&&hash1[t]!=x)
    {
        t++;
        if(t==M) t=0;
    }
    return t;
}
```
### 1.3 深度优先搜索-DFS
由于本题每个地雷或者排雷火箭的引爆，会导致其范围内的其他地雷连锁引爆，因此我们可以考虑在每一个排雷火箭引爆点进行dfs查找下一个地雷的位置，再有下一个地雷的位置递归的查找下下个地雷的位置。找到下一个地雷位置之后，统计该点的地雷个数，最后汇总便是最后答案。

### 时间复杂度近似为O(r^2n+m)
```
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int M = 999997;
const int Base = 1e9 + 1;

int res;
LL hash1[M]; //hash1用于维护find函数
int hash2[M],hash3[M],book[M]; //hash2:地雷在某点的出现次数 hash3:某点的地雷半径 book:标记该点是否被搜索

//Base进制编码降维
LL get_key(int x,int y)
{
    return (LL)x * Base + y;
}

//手写哈希函数
int find(LL x)
{
    int t = (x % M + M) % M;
    while(hash1[t]!=-1&&hash1[t]!=x)
    {
        t++;
        if(t==M) t=0;
    }
    return t;
}

//判断(x2,y2)是否位于(x1,y1,r1)的范围内
bool judge(int x1,int y1,int x2,int y2,int r)
{
    int d = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
    return d <= r*r;
}

//dfs
void dfs(int x,int y,int r)
{
    for(int i=-r;i<=r;i++)
        for(int j=-r;j<=r;j++)
        {
            int dx = x + i;
            int dy = y + j;
            LL t = get_key(dx,dy);
            if(hash2[find(t)]&&judge(x,y,dx,dy,r)&&!book[find(t)])
            {
                res += hash2[find(t)]; //答案加上该点地雷个数
                book[find(t)] = 1; //标记为已搜索
                dfs(dx,dy,hash3[find(t)]); //搜索下一个点
            }
        }
    return;
}

int main()
{
    int n,m;
    cin>>n>>m;
    memset(hash1,-1,sizeof hash1); //hash1初始化为空
    for(int i=0;i<n;i++)
    {
        int x,y,r;
        cin>>x>>y>>r;
        LL t = get_key(x,y);
        hash1[find(t)] = t; //维护哈希函数
        hash2[find(t)]++; //统计该点地雷数量
        hash3[find(t)] = max(r,hash3[find(t)]); //记录该点地雷半径的最大值
    }
    
    for(int i=0;i<m;i++)
    {
        int x,y,r;
        cin>>x>>y>>r;
        dfs(x,y,r); //从每一个排雷火箭引爆点开始dfs
    }
    cout<<res<<endl;
    return 0;
}
```

0.0分

19 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

许健跃

TA的其他文章

你可能喜欢

蛇行矩阵（C++代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C二级辅导-温度转换（C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

蓝桥杯2022年第十三届省赛-扫雷(dfs+手写哈希)--技巧总结

评论区

精彩推荐

简单编码（C++代码）（这里推荐用switch）

【蟠桃记】（C++代码）（递归计算）

C语言训练-求PI* （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

【偶数求和】（C++代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

简单的for循环

1113题解

Hello, world! （C语言代码）

许健跃

TA的其他文章

你可能喜欢

蛇行矩阵 （C++代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C二级辅导-温度转换 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

蓝桥杯2022年第十三届省赛-扫雷(dfs+手写哈希)--技巧总结

评论区

精彩推荐

简单编码 （C++代码）（这里推荐用switch）

【蟠桃记】 （C++代码）（递归计算）

C语言训练-求PI* （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题11.11 （C语言代码）

【偶数求和】 （C++代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

简单的for循环

1113题解

Hello, world! （C语言代码）

蛇行矩阵（C++代码）

C二级辅导-温度转换（C语言代码）

　　评论区

简单编码（C++代码）（这里推荐用switch）

【蟠桃记】（C++代码）（递归计算）

【偶数求和】（C++代码）