1 条题解

  • 0
    @ 2023-11-4 20:16:51

    此题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
    上传者