题目大意
另类的“扫雷”游戏，给出若干个地雷的信息（横坐标、纵坐标、自动爆炸时间），另外规定，每一分钟，可以人为地指定任意一颗地雷爆炸，并且地雷爆炸会引发同行、同列所有距离k以内的地雷爆炸，从而产生连锁反应。试问引爆地图上所有地雷所需要的最少时间是多少。
题目分析
首先我们知道的是，每一颗地雷爆炸的形式有三种：
- 到达一定时间自动爆炸
- 被其他的地雷引爆
- 人为引爆
如果单纯一个一个考虑三个条件，将会使本题变得十分复杂。那么，我们可不可以将三个条件作出一定的简化，或者合并一下，从而使得问题处理起来更加简便而清晰呢？
当然是可以的。
- 根据题意，地雷的连锁引爆无疑是本题的关键之处；这一部分的处理，需要用到深度优先搜索DFS；
- 任何一颗地雷的爆炸都不是单纯它一个的爆炸，还需要考虑它引发的所有地雷的爆炸；这样一来，这些被同一颗地雷引爆的所有地雷的爆炸时间全部都是一样的，可以将它们看作一个整体。
- 那么怎么找到这样的整体呢？事实上，这样的地雷群体，只要其中任意一个爆炸，整个群体都会爆炸，也就是说，对任何一颗地雷进行DFS，都可以牵扯出整个地雷群；
- 还需要另设一个标记，记录哪些地雷已经爆炸过。
具体实现
由于地雷坐标实在太大，不方便直接使用二维数组存储相关信息，我们可以换一种方式存储：使用map容器，存储每一横行和每一纵列的地雷的坐标，这样也方便后续的DFS处理。
另外，设置容器记录每一颗地雷的爆炸时间以及是否爆炸；
// 存储指定坐标下，一整行（列）的地雷坐标
map<ll, vector<ll>>mapX;
map<ll, vector<ll>>mapY;
map<pair<ll, ll>, bool>isBoo;
map<pair<ll, ll>, ll>times;
...
while (i<n)
{
scanf("%lld%lld%lld", &x, &y, &t);
alls[i++]=make_pair(x, y);
mapX[x].push_back(y);
mapY[y].push_back(x);
times[{x, y}] = t;
}
...对所有地雷遍历，也就是上面说过的，任意一个地雷爆炸可以牵扯出整个地雷群，只需要求出这个地雷群的最短爆炸时间即可，用到DFS：
ll dfs(ll x, ll y)
{
// 让{x,y}处地雷爆炸
ll minT = times[{x, y}];
isBoo[{x, y}] = true;
// 连锁反应爆炸开始
auto i = lower_bound(mapX[x].begin(), mapX[x].end(), y);
auto j = lower_bound(mapY[y].begin(), mapY[y].end(), x);
// 四个方向
if (++i != mapX[x].end() && !isBoo[{x, * i}] && abs(*i - y) <= k)
{
ll tm = dfs(x, *i);
minT = minT > tm ? tm : minT;
}
i--;
if (i != mapX[x].begin() && !isBoo[{x, * (--i)}] && abs(*i - y) <= k)
{
ll tm = dfs(x, *i);
minT = minT > tm ? tm : minT;
}
if (++j != mapY[y].end() && !isBoo[{*j, y}] && abs(*j - x) <= k)
{
ll tm = dfs(*j, y);
minT = minT > tm ? tm : minT;
}
j--;
if (j != mapY[y].begin() && !isBoo[{*(--j), y}] && abs(*j - x) <= k)
{
ll tm = dfs(*j, y);
minT = minT > tm ? tm : minT;
}
return minT;
}这样一来，所有的地雷所需爆炸时间就会被分开，在数组中的每一个值都代表一个不同的地雷群的爆炸时间，也就是说，它们互不影响（地雷群之间不会因为爆炸而相互引爆了，否则两个地雷群会合成一个）。采用双指针对这个时间数组进行遍历，以时间为循环变量，直到双指针相遇即可。
vector<ll> pres;// 存储dfs的结果，得到的就是所有地雷群的爆炸时间
for (int i=0;i<alls.size()-1;i++)
{
auto e = alls[i];
if(!isBoo[e])
pres.push_back(dfs(e.first, e.second));
}
// 需要对pres进行升序排序，最后面的地雷当然需要每一次的人为引爆
sort(pres.begin(), pres.end());
// 设置头指针sp，尾指针ep，ans就是最后的答案————爆炸完的最短时间
ll ep = pres.size() - 1, sp = 0, ans = 0;
for (;; ans++)
{
while (pres[sp] == ans) sp++;
if (ep <= sp) break;
ep--;
}
cout << ans << endl;完整代码
// unusualmineSweeper.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
typedef long long ll;
using namespace std;
// 存储指定坐标下，一整行（列）的地雷坐标
map<ll, vector<ll>>mapX;
map<ll, vector<ll>>mapY;
map<pair<ll, ll>, bool>isBoo;
map<pair<ll, ll>, ll>times;
ll x, y, k, t;
int q, n;
ll dfs(ll x, ll y)
{
// 让{x,y}处地雷爆炸
ll minT = times[{x, y}];
isBoo[{x, y}] = true;
// 连锁反应爆炸开始
auto i = lower_bound(mapX[x].begin(), mapX[x].end(), y);
auto j = lower_bound(mapY[y].begin(), mapY[y].end(), x);
// 四个方向
if (++i != mapX[x].end() && !isBoo[{x, * i}] && abs(*i - y) <= k)
{
ll tm = dfs(x, *i);
minT = minT > tm ? tm : minT;
}
i--;
if (i != mapX[x].begin() && !isBoo[{x, * (--i)}] && abs(*i - y) <= k)
{
ll tm = dfs(x, *i);
minT = minT > tm ? tm : minT;
}
if (++j != mapY[y].end() && !isBoo[{*j, y}] && abs(*j - x) <= k)
{
ll tm = dfs(*j, y);
minT = minT > tm ? tm : minT;
}
j--;
if (j != mapY[y].begin() && !isBoo[{*(--j), y}] && abs(*j - x) <= k)
{
ll tm = dfs(*j, y);
minT = minT > tm ? tm : minT;
}
return minT;
}
int main()
{
scanf("%d", &q);
while (q--)
{
mapX.clear();
mapY.clear();
isBoo.clear();
scanf("%d%lld", &n, &k);
vector<pair<ll, ll>> alls(n+1); // 存放全部地雷的坐标对
int i = 0;
while (i<n)
{
scanf("%lld%lld%lld", &x, &y, &t);
alls[i++]=make_pair(x, y);
mapX[x].push_back(y);
mapY[y].push_back(x);
times[{x, y}] = t;
}
for (auto item : mapX)
{
sort(mapX[item.first].begin(), mapX[item.first].end());
}
for (auto item : mapY)
{
sort(mapY[item.first].begin(), mapY[item.first].end());
}
vector<ll> pres;
for (int i=0;i<alls.size()-1;i++)
{
auto e = alls[i];
if(!isBoo[e])
pres.push_back(dfs(e.first, e.second));
}
sort(pres.begin(), pres.end());
ll ep = pres.size() - 1, sp = 0, ans = 0;
for (;; ans++)
{
while (pres[sp] == ans) sp++;
if (ep <= sp) break;
ep--;
}
cout << ans << endl;
}
}
