本题和ccf csp-201409-4-最优配餐、ccf csp-201604-4-游戏有相似之处,但是最优配餐和游戏在进行bfs图的遍历时,都是类似于 马踏棋盘,会一层一层遍历棋盘上每个点。
而 本题的bfs遍历,是有条件的遍历:
1、走的是有定义(该点放置有无线路由器)的点(xi,yi)
2、半径在r之内
所以本题需要用结构体数组记录图的信息
,结构体数组下标表示路由器的编号
。
(输入中所有的坐标的绝对值不超过 108)
代码如下
#include
#include
using namespace std;
const int N = 205;
struct node{
long long x,y;
int cross;
}map[N];
queue q;
long long n,m,k,r;
bool vis[N];
int bfs(){
vis[1] = true;
q.push({map[1].x,map[1].y,0});
while(!q.empty()){
node cur = q.front();
q.pop();
if(cur.x==map[2].x&&cur.y==map[2].y) return cur.cross-1;
for(int i = 1; i r*r) continue;
vis[i] = true;
q.push({map[i].x,map[i].y,cur.cross+1});
}
}
}
int main()
{
int x,y;
cin >> n >> m >> k >> r;
for(int i = 1; i > map[i].x >> map[i].y;
}
int ans = bfs();
printf("%d\n", ans);
return 0;
}