奶酪（bfs）

题目描述

现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以认为是无限大的，奶酪 中间有许多 半径相同 的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中， 奶酪的下表面为z=0，奶酪的上表面为z=h。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐 标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在 不破坏奶酪 的情况下，能否利用已有的空洞跑 到奶酪的上表面去?

空间内两点P1(x1,y1,z1)、P2(x2,y2,z2)的距离公式如下：

dist(P1,P2)=(x1−x2)2+(y1−y2)2+(z1−z2)2−−−−−−−−−−−−−−−−−−−−−−−−−−−−√

输入输出格式
输入格式：

每个输入文件包含多组数据。

第一行，包含一个正整数 T，代表该输入文件中所含的数据组数。

接下来是 T组数据，每组数据的格式如下： 第一行包含三个正整数 n,h 和 r，两个数之间以一个空格分开，分别代表奶酪中空 洞的数量，奶酪的高度和空洞的半径。

接下来的 n行，每行包含三个整数 x,y,z，两个数之间以一个空格分开，表示空 洞球心坐标为(x,y,z)。
输出格式：

T行，分别对应 T 组数据的答案，如果在第 i组数据中，Jerry 能从下 表面跑到上表面，则输出Yes，如果不能，则输出No （均不包含引号）。
输入输出样例
输入样例#1：

3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4

输出样例#1：

Yes
No
Yes

说明
【输入输出样例 1 说明】

第一组数据,由奶酪的剖面图可见：

第一个空洞在(0,0,0)

与下表面相切

第二个空洞在(0,0,4)
与上表面相切 两个空洞在(0,0,2)

相切

输出 Yes

第二组数据,由奶酪的剖面图可见：

两个空洞既不相交也不相切

输出 No

第三组数据,由奶酪的剖面图可见：

两个空洞相交 且与上下表面相切或相交

输出 Yes

【数据规模与约定】

对于 20%
的数据,n=1,1≤h , r≤10,000,坐标的绝对值不超过 10,000。

对于 40%
的数据,1≤n≤8, 1≤h , r≤10,000,坐标的绝对值不超过 10,000。

对于80%
的数据, 1≤n≤1,000, 1≤h,r≤10,000,坐标的绝对值不超过10,000。

对于 100%
的数据,1≤n≤1,000,1≤h,r≤1,000,000,000,T≤20,坐标的 绝对值不超过 1,000,000,000。

解题报告
题意理解

一句话题意:你要从最低点走到最高点,你必须从与下边界联通的洞孔开始走,而且每次只能走到和你所在奶酪相连通的奶酪.对于两个奶酪而言,他们的距离必须小于2×r,才被认为是相通的.

空间内两点P1(x1,y1,z1)、P2(x2,y2,z2)的距离公式如下：
dist(P1,P2)=(x1−x2)2+(y1−y2)2+(z1−z2)2−−−−−−−−−−−−−−−−−−−−−−−−−−−−√

条件性质

这道题目的条件就是:连通性&两点之间距离公式.
这道题目的性质:还是上面所说的连通性.即两个奶酪必须连通,才可以转移
算法判断

这道题目我们初步一看,发现特别的繁琐,然而实际上这道题目就是一道平面直角坐标系走迷宫问题.
对于走迷宫问题,显然BFS广度优先搜索是我们的不二选择.
解析算法

首先对于一道搜索题目而言的话,我们还是有基本的三点目标

目标一:方向指示数组: 对于这道题目而言,显然每一个和它相连通的洞都可以,所以这道题目的方向指示数组形同虚设.

目标二:边界处理: 对于这道题目而言,我们的坐标其实也没有什么要求,因为连通已经包含了所有的条件.

目标三:拓展准则: 每一道搜索题目,难点往往都在这个拓展准则上面,这道题目也不例外,我们发现,这道题目的拓展准则也就是题目中连通性,只要两个点是连通的,那么我们就可以拓展.

      #include <bits/stdc++.h>
      using namespace std;
      const int N=1e4;
      struct node
      {
         double x,y,z;//double类型要注意
      } a[N];
      int vis[N],n,h,r,t;
      queue<node> q,kong;
      double dist(node a,node b)//计算两点之间的距离,也就是题目描述中给出的公式.
      {
         double nx=a.x-b.x,ny=a.y-b.y,nz=a.z-b.z;
         double ans=sqrt(nx*nx+ny*ny+nz*nz);
         return ans;
      }
      int bfs(void)
      {
         while(q.size())
          {
             if (q.front().z+r>=h)//如果满足条件.
                 return true;
              node now=q.front();
              q.pop();
             for(int i=1; i<=n; i++)//所有的点都可以成为下一步的拓展.
              {
                 if (r*2>=dist(now,a[i]) && !vis[i])//如果两点的距离<=2*r,而且这个点没有访问过.
                  {
                      q.push(a[i]);//入队
                      vis[i]=1;//已经访问过了
                     if (q.front().z+r>=h)//如果满足条件,那么显然可以返回true
                         return true;
                  }
              }
          }
         return false;//找不到合法路径
      }
      int main()
      {
          ios::sync_with_stdio(false);//读入优化,防止超时.
          cin>>t;
         while(t--)
          {
              cin>>n>>h>>r;
             for(int i=1; i<=n; i++)
                  cin>>a[i].x>>a[i].y>>a[i].z;
              q=kong;//初始化
             memset(vis,false,sizeof(vis));//初始化不可少
             for(int i=1; i<=n; i++)
                 if (a[i].z-r<=0)//如果和下边界接触
                      q.push(a[i]),vis[i]=1;//才可以入队
             if (bfs())//判断是否找得到合法路径
                  cout<<"Yes";
             else
                  cout<<"No";
              cout<<endl;
          }
         return 0;
      }
  
 

  
 
 

上面这个解法在有的平台上AC了但是其他有的PAC

所以我们有了下面这个并查集方法

      #include<bits/stdc++.h>
      using namespace std;
      typedef long long LL;
      LL T;
      LL n, h, r;
      LL p[2000];
      LL top[2000], back[2000];
      struct code{ // 储存奶酪空间上的三个坐标
          LL x, y, z;
      }num[2000];
      LL rrh(LL q,LL p){ // 欧几里得空间距离公式（返回距离平方，刚刚一位秦仁兄PAC可能就是double精度不够的原因）
          LL a = (num[q].x - num[p].x) * (num[q].x - num[p].x);
          LL b = (num[q].y - num[p].y) * (num[q].y - num[p].y);
          LL c = (num[q].z - num[p].z) * (num[q].z - num[p].z);
         return a + b + c;
      }
      LL find(LL x){ // 并查集 + 路径压缩
         if(p[x] != x) p[x] = find(p[x]);
         return p[x];
      }
      int main(){
         scanf("%lld", &T);
         while( T-- ){
             memset(back,0, sizeof back);
             memset(top, 0, sizeof top);
             scanf("%lld %lld %lld", &n, &h, &r);
             for(LL i = 1; i <= n; i ++) p[i] = i; // 并查集初始化
             for(LL i = 1; i <= n; i ++){
                  LL a,b,c;
                 scanf("%lld %lld %lld", &a, &b, &c);
                  num[i]={a, b, c};
              }
             for(LL i = 1; i <= n; i ++){
                 for(LL j = 1; j < i; j ++){
                     if(rrh(i, j) <= 4*r*r){
                         // 将两个奶酪的距离平方，提高精度（非常好的想法）
                          p[find(i)] = find(j);
                         // 将相交或相切的奶酪加入一个联通块
                      }
                  }
              }
             bool flag = false;
             for(LL i = 1; i <= n; i ++){
                 if(num[i].z - r <= 0) back[find(i)] = 1;
                 if(num[i].z + r >= h) top[find(i)] = 1;
                 // 将与 底面 或 顶部 相交的联通块的 祖宗节点 设为真
              }
             for(LL i = 1; i <= n; i ++){
                 if(back[i] == 1 && top[i] == 1){
                     // 如果同一个联通块既与底面相交又与顶部相交，连同在一起，一同全通，并查集的大大优势
                      flag = true; // 则 祖宗节点 为真，退出循环
                     break;
                  }
              }
             if(flag == true) puts("Yes");
             else puts("No");
          }
         return 0;
      }
  
 

  
 
 

LL find(LL x){ // 并查集 + 路径压缩
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

find p[x]太帅了！

文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_54227557/article/details/120608366