题解 | OhThoseRollers-牛客假日团队赛7A题

题目描述

Farmer John has installed a new winch that gives him mechanical advantage when lifting bales of hay into the barn. The winch was manufactured by the Rube Goldberg Winch Company and has way too many rollers to make any sense at all. The winch has a huge steel plate with a number of rollers whose ultimate source of power is the drive-roller whose location FJ has denoted as the origin (0,0). This roller drives a roller that drives another roller, etc. etc. until the final roller is driven. FJ is trying to find that final roller and wants to know which one it is.
FJ has recorded the $x_i,y_i (-5,000 \leq x_i \leq 5,000; -5,000\leq y_i \leq 5,000)$ coordinates and the radius $r_i (3 \leq r_i \leq 1024)$ of each of the $N (2 \leq N \leq 1080)$ rollers. Tell him the x,y coordinate of the last roller in the chain (the roller that is driven but drives no other roller). Every roller except the drive-roller is driven by exactly one other roller.

输入描述:

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 describes roller i with three space separated integers: $x_i, y_i,$ and $r_i$

输出描述:

* Line 1: A single line with two space-separated integers that are respectively the x,y coordinates of the last roller in the chain of driven rollers.

示例1

输入

3
0 0 30
30 40 20
-15 100 55

输出

-15 100

说明

Three rollers. First is at the origin with radius 30. It drives the roller at (30,40) whose radius is 20. That roller in turn drives the third roller located at (-15,100) with radius 55.

解答

不了解BFS的同学只会用DFS，嘻嘻，我当时拿到这道题一想就是用dfs找连通终点，但是忽略的如果有环怎么办呢？最后队友提醒我了，分层次遍历什么意思呢？（以前我明明看过啊哈算法的BFS 但是没怎么理解，但是现在我理解了，而且我发现bfs很有用对于层次搜索!!）
就这道题来说:

如果是这样的齿轮呢？那么应该输出什么？我当时就用的dfs结果输出的就是D点（因为我是按照题上输出顺序遍历的），很明显我的想法错了，因为结果为C点，之后我想了想，如果我们从A点开始把与A点连通的点找出来是B,D点，那么我们就可以利用B去找与B的连通点，之后D点也同样这样。那么这不就是典型的BFS吗？
我现在还是来加深一下什么是BFS：
我们有一个图：

那么我们利用队列来处理这个问题。首先我们把A点入队（这里可以用结构体哟（下标））然后去找与A点连通的顶点并且一个一个入队（注意：这里只能从B,C,D这样入队因为这种习惯是好事（因为后面遍历的时候就不会乱了））就成了下图的样子了。

然后出队A点，因为他已经是第一层用完了。那么就成了：在这里插入图片描述

之后按照同样的方法这样下去直到队空。
但是怎么实现这个方法呢？
这里用到了while（）+层次遍历(经常爱思考的我相信一定想的出来)(注意找起点（0,0）和记录最后一个队列值);

#include<map>
#include<list>
#include<ctime>
#include<queue>
#include<deque>
#include<cmath>
#include<stack>
#include<string>
#include<cstdlib>
#include<cstring>
#include <iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//ll gcd(ll a,ll b){
//   return b?gcd(b,a%b):a;
//}
//ll QP(ll x,ll n,ll Mod){
//     ll res=1;
//     while(n){
//       if(n&1){
//         res=(res*x)%Mod;
//       }
//       x=(x*x)%Mod;
//       n>>=1;
//     }
//       return res;
//}A题 
ll n,book[1099];
ll sp,ans;
struct Point{
 ll x,y,r;
}p[1099];
ll D(Point a,Point b){
	  return  (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
ll R(Point a,Point b){
	  return (a.r+b.r)*(a.r+b.r);
}
void  bfs(){
	  queue<ll> q;
	  q.push(sp);
	  book[sp]=1;
	  while(!q.empty()){
	  	  ll now=q.front();
			q.pop();
	  	  for(int i=0;i<n;i++){
	  	  	    if(now!=i&&book[i]!=1&&D(p[now],p[i])==R(p[now],p[i])){//book[]用来标记这个点走过没，因为你不可能又原路返回找图吧，D和R两个函数用来判断是不是可以到达的。
	  	  	          ans=i;
	  	  	          book[i]=1;
					  q.push(i);    	  
					}
			}
	  }
}
int main(){
  scanf("%lld",&n);
  for(int i=0;i<n;i++){
  	  cin>>p[i].x>>p[i].y>>p[i].r;
  	  if(p[i].x==p[i].y&&p[i].y==0){
  	  	  sp=i; //记录开始下标
		}
  }
  bfs();
  printf("%lld %lld\n",p[ans].x,p[ans].y);
	return 0;
}

来源：Forward in time