无线网络
程序员文章站
2022-06-06 12:10:26
...
用到的是广度优先搜索 ,按层次遍历。
记录后来添加路由器的数量,我使用了一个add_number数组,这个量不能笼统的计数,必须是相对于路径上的上一个点。
碰到的两个坑:
一是自作聪明,将判断距离那,R*R 没考虑到超过最大整数
二是cin 比scanf运行时间长很多 真的!
#include<iostream>
#include <queue>
#include<math.h>
#define MAXN 200
using namespace std;
int N, M, K, R;
bool graph[MAXN][MAXN]; //图的邻接矩阵
int pos[MAXN][2]; //存放路由器的点坐标
bool ifedge(int a, int b) //判断a,b两点是否有边(是否可以建立网络连接)
{
return sqrt(pow(pos[a][0]-pos[b][0],2)+pow(pos[a][1]-pos[b][1],2))<=R;
}
int bfs()
{
bool visited[M+N] ={0};
int add_number[MAXN] = {0}; //记录遍历到第i个路由器时 用到添加路由器的个数
queue<int> q;
q.push(0);
int len = 1,nextlen, level = 1; //level 记录遍历的层次 len表示这一层次的个数 add_number记录添加路由器的个数
while(1) //由题知 输入数据保证第 1 和第 2 个路由器在仅有这 n 个路由器的情况下已经可以互相连接
{
nextlen =0;
for(int l =0; l<len; l++)
{
int temp = q.front();
if(temp == 1) return level-2;
q.pop();
for(int i=0; i<N; i++)
{
if(graph[temp][i] && !visited[i])
{
q.push(i);
visited[i] = true;
nextlen++;
}
}
for(int i=N; i<N+M ; i++)
{
if(graph[temp][i] && !visited[i] && add_number[temp]<K)
{
q.push(i);
visited[i] = true;
add_number[i] = add_number[temp]+1;
nextlen++;
}
}
}
len = nextlen;
level++ ;
}
}
int main()
{
cin>>N>>M>>K>>R;
for(int i=0; i<N+M; i++)
cin>>pos[i][0]>>pos[i][1];
for(int i=0; i<N+M; i++)
for(int j=i+1; j<N+M; j++)
graph[i][j] = graph[j][i] = ifedge(i, j);
cout<<bfs();
return 0;
}