AcWing 4407.扫雷

思路：DFS+二分

通过对于题目的理解，我们知道，这个题是典型的DFS，因为这里的地雷都是连锁反应进行爆炸的，所以我们可以用DFS来遍历。

思路就是对于每一个火箭进行遍历坐标，遍历到一个火箭的坐标之后看看它的范围内有没有地雷，有的话就是地雷炸了，然后换做以这个炸了的地雷为起点，看看其他地雷炸了没有。暴力DFS是这个样子：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_set>
#include<set>
#define int long long
#define MAX 5010
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
queue<PII>q;
struct Node {
    int x;
    int y;
    int r;
}lei[MAX],rocket[MAX];
bool flag[MAX];
bool cmp(Node a, Node b) {
    return a.x < b.x;
}
double dis(Node a, Node b) {
    return sqrt(abs((a.x - b.x)) * abs((a.x - b.x)) + abs(a.y - b.y) * abs(a.y - b.y));
}
void dfs(Node u) {
    _for(i, 1, n + 1) {
        if (!flag[i] && dis(u, lei[i]) <= u.r) {
            flag[i] = 1;
            counts++;
            dfs(lei[i]);
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    _for(i, 1, n + 1)
    {
        cin >> lei[i].x >> lei[i].y >> lei[i].r;
    }
    _for(i, 1, m + 1)
        cin >> rocket[i].x >> rocket[i].y >> rocket[i].r;
    _for(i, 1, m + 1) {
        dfs(rocket[i]);
    }
    cout << counts;
    return 0;
}

OK，这样的话是会超时的，因为这个DFS做法的范围顶多就到1000数据这里，而题目中的要求是到5e4的数据。所以我们需要进行优化。

由于我们遍历的时候似乎把范围扩大的有点多了，比如，如果说一个地雷不在火箭的范围内，我们还是进行了判断和遍历，这个时候其实就已经耗费了很长时间。所以，其实优化也就是对于DFS的范围进行了缩减，也就是你们常说的剪枝。我们怎么剪枝？

我们发现，在这个(x-r,x+r)的范围内是可以引爆地雷的，也就是说，我们提前给出了范围，事先排除掉其他不符合范围i的地雷，也就是做了一个预处理，然后我们再去判断在这个范围内的地雷怎么连锁爆炸，然后统计个数。

这时你应该会想到一个技巧，就是二分，我们肯定应该从近距离到远距离进行判断呀，这样才能保证我们每一次的选择都是最佳的，也是更保险的做法。

在AcWing上，这里的会卡到最后一个50000的数据，这样的话大家就去看哈希的做法吧，这里就不详细讲述了。

上代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_set>
#include<set>
#define int long long
#define MAX 50010
#define _for(i,a,b) for(int i=a;i<(b);i++)
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef pair<int, int> PII;
int n, m;
int counts;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
queue<PII>q;
struct Node {
    int x;
    int y;
    int r;
}lei[MAX],rocket[MAX];
bool flag[MAX];
bool cmp(Node a, Node b) {
    return a.x < b.x;
}
double dis(Node a, Node b) {
    return sqrt(abs((a.x - b.x)) * abs((a.x - b.x)) + abs(a.y - b.y) * abs(a.y - b.y));
}
void dfs(Node u) {
    int l = 0;
    int r = n - 1;
    int lmid = 0;
    int rmid = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (lei[mid].x < u.x - u.r)
            l = mid + 1;
        else if (lei[mid].x == u.x - u.r)
            break;
        else
            r = mid - 1;
    }
    lmid = l;
    l = 0;
    r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (lei[mid].x > u.x + u.r)
            r = mid - 1;
        else if (lei[mid].x == u.x + u.r)
            break;
        else
            l = mid + 1;
    }
    rmid = r;
    _for(i, lmid, rmid + 1) {
        if (!flag[i] && dis(u, lei[i]) <= u.r) {
            flag[i] = 1;
            counts++;
            dfs(lei[i]);
        }
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    _for(i, 0, n)
    {
        cin >> lei[i].x >> lei[i].y >> lei[i].r;
    }
    _for(i, 0, m)
        cin >> rocket[i].x >> rocket[i].y >> rocket[i].r;
    sort(lei, lei + n, cmp);
    _for(i, 0, m) {
        dfs(rocket[i]);
    }
    cout << counts;
    return 0;
}