http://hihocoder.com/problemset/problem/1307
首先，如果左、右边界被圆分离开，就意味着无法穿越雷区。
把上、下边界以及N个圆抽象成N+2个图节点，当边界与圆或圆与圆之间相交时表示它们连通，问题就转变为判断从上边界到下边界是否存在路径。建图后从上边界跑一遍DFS即可。
#include <iostream> #include <cstdio> #include <vector> #include <string> #include <map> #include <set> #include <cmath>using namespace std;struct Circle {long long x, y, r; }circles[1005];int W, H, N;vector<vector<int> > adj;bool intersect(Circle& a, Circle& b) {return ( sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) ) - (a.r+b.r) <= 0 ); }void dfs(int cur, vector<bool>& vis) {vis[cur] = true;for (int i = 0; i < adj[cur].size(); ++i) {int to = adj[cur][i];if (!vis[to]) {dfs(to, vis);}} }void solve() {adj = vector<vector<int> >(N+2);int s = 0, t = N+1;// up (0)for (int i = 1; i <= N; ++i) {if (circles[i].y + circles[i].r >= H) {adj[s].push_back(i);}if (circles[i].y - circles[i].r <= 0) {adj[i].push_back(t);}}for (int i = 1; i < N; ++i) {for (int j = i + 1; j <= N; ++j) {if (intersect(circles[i], circles[j])) {adj[i].push_back(j);adj[j].push_back(i);}}}// DFSvector<bool> vis(N+2, false);dfs(s, vis);if (vis[t]) {cout << "NO" << endl;} else {cout << "YES" << endl;} }int main() {int T;cin >> T;for (int i = 0; i < T; ++i) {cin >> W >> H >> N;for (int j = 1; j <= N; ++j) {scanf("%lld%lld%lld", &circles[j].x, &circles[j].y, &circles[j].r);}solve();}return 0; }