返回题解分享
讨论 / 题解分享/ 帖子详情

扫雷(编程题) - 题解

// https://dashoj.com/d/lqbproblem/p/89
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
ll n, m, ans = 0;
map<PLL, PLL> g; //
map<PLL, ll> cnt;
queue<pair<PLL, PLL>> qp; //

int main() {
	// in
	cin >> n >> m;
	for (ll i = 0; i < n; i++) {
		ll x1, y1, r1;
		cin >> x1 >> y1 >> r1;
		if (g.count({x1, y1})) g[{x1, y1}] = {max(g[{x1, y1}].first, r1), 1};
		else g[{x1, y1}] = {r1, 1};
		cnt[{x1, y1}]++;
	}
	for (ll i = 0; i < m; i++) {
		ll x2, y2, r2;
		cin >> x2 >> y2 >> r2;
		qp.push({{x2, y2}, {r2, 1}});
		while (!qp.empty()) { //
			pair<PLL, PLL> node = qp.front();
			qp.pop();
			ll x = node.first.first, y = node.first.second, r = node.second.first;
			for (ll xx = x - r; xx <= x + r; xx++)
				for (ll yy = y - r; yy <= y + r; yy++) {
					if (g.count({xx, yy}) && g[{xx, yy}].second && (xx - x) * (xx - x) + (yy - y) * (yy - y) <= r * r) {
						g[{xx, yy}].second = 0;
						qp.push({{xx, yy}, {g[{xx, yy}].first, 0}});
						ans+= cnt[{xx, yy}];
					}
				}
		}
	}
	cout << ans << endl;
	return 0;
}
0 回复 0 转发 0 喜欢 3 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!