当前位置： 移动技术网 > 移动技术>移动开发>IOS > 试题编号： 201403-4 试题名称： 无线网络

试题编号： 201403-4 试题名称： 无线网络

2020年08月10日  | 移动技术网移动技术  | 我要评论 
#include<bits/stdc++.h>
using namespace std;
struct node{
    long long x;
    long long y;
    int step;
    int rest_k;
};
bool visited[1005];
int xx[1005];
int yy[1005];
int sx,sy,fx,fy;
int main(){
    ios::sync_with_stdio(0);
    long long r;
    int n,m,k;cin >> n >> m >> k >> r;
    for(int i = 0;i < n;i++){
        int a,b;
        cin >> a >> b;
        if(i == 0){
            sx = a;
            sy = b;
        }
        if(i == 1){
            fx = a;
            fy = b;
        }
        xx[i] = a;
        yy[i] = b;
    }

    for(int i = n;i < n+m;i++){
        int a,b;cin >> a >> b;
        xx[i] = a;
        yy[i] = b;
    }

    queue<node> Q;
    node temp;
    temp.x = sx;
    temp.y = sy;
    temp.rest_k = 0;
    temp.step = 0;
    Q.push(temp);
    visited[0] = 1;
    while(!Q.empty()){
        node top = Q.front();
        Q.pop();
        //cout << top.x << " " << top.y << " " << top.step << " " << top.rest_k << endl;
        for(int i = 0;i < n;i++){
            if(!visited[i]){
                long long nx = xx[i];
                long long ny = yy[i];
                long long dx = top.x - nx;
                long long dy = top.y - ny;
                if(dx*dx + dy*dy <= r*r){
                    if(i == 1){
                        cout << top.step << endl;
                        return 0;
                    }
                    visited[i] = 1;
                    temp.rest_k = top.rest_k;
                    temp.step = top.step + 1;
                    temp.x = nx;
                    temp.y = ny;
                    Q.push(temp);
                }
            }
        }
        if(top.rest_k >= k) continue;
        for(int i = n;i < n + m;i++){

            if(!visited[i]){
                long long nx = xx[i];
                long long ny = yy[i];
                long long dx = top.x - nx;
                long long dy = top.y - ny;
                if(dx*dx + dy*dy <= r*r){
                    if(i == 1){
                        cout << top.step << endl;
                        return 0;
                    }
                    visited[i] = 1;
                    temp.rest_k = top.rest_k + 1;
                    temp.step = top.step + 1;
                    temp.x = nx;
                    temp.y = ny;
                    Q.push(temp);
                }
            }
        }
    }
}

本文地址：https://blog.csdn.net/qq_43251559/article/details/107890225

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网