1 条题解
-
0
此题bfs即可
对于第一个人,搜索其他与它距离不超过d的人,对于搜索到的这些人,再搜索与他们距离不超过d且之前没被搜索的人,一直重复这个过程,用队列维护这个过程即可
参考代码:
#include<iostream> #include<queue> using namespace std; int x[2001], y[2001]; bool v[2001]; //记录第i个人是否符合条件 bool cmp(int i, int j, int d) //比较第i个坐标与第j个坐标的距离,小与d则返回true { return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) <= d * d; } int main() { int n, d; cin >> n >> d; for (int i = 1; i <= n; i++) cin >> x[i] >> y[i]; queue<int>q; q.push(1), v[1] = 1; while (!q.empty()) { int k = q.front(); q.pop(); for (int i = 1; i <= n; i++) { if (v[i] == 0 && cmp(k, i, d)) v[i] = 1, q.push(i);//如果第i个人符合条件,则放入队列中 } } for (int i = 1; i <= n; i++) { if (v[i]) cout << "哇哦\n"; else cout << "炉石传说真nm好玩!\n"; } return 0; }
- 1
信息
- ID
- 918
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 287
- 已通过
- 26
- 上传者