NOIP2017提高组day2T1题解（奶酪）

题目链接：奶酪

这道题还是很水的，在下拿了满分。

并没有用什么高级的算法，我讲一下基本思路。

我们把每个洞都视为一个节点。

我们读入相关数据后，就先进行预处理，通过每个节点的信息和题目的规定，建立一张无向图，两个能相通的洞对应的节点之间有一条无向边，这样我们就建立好了一张图。

在建图的时候，我们还需要干一件事，那就是记录哪些是起点，哪些是终点。

接下来我们就对每一个节点进行bfs就行了，这样就可以了。

我们再结合代码讲解一下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
//保险起见，没用万能头文件
using namespace std;
//手写队列，用于bfs
struct gque{
int f,t;
int num[1050];
void init(){
f=0;t=0;
}
void gpush(int n){
num[t++]=n;
}
int gtop(){
return num[f];
}
void gpop(){
f++;
}
};
gque q;
int T;
int n,h,r;
//保存图
vector<int> mapp[1005];
//保存起点
vector<int> s;
//保存终点（这样便于判断）
int tvis[1005];
int indd[1005][3];
int vis[1005];
int sflag,tflag;
int flag;
//计算两点距离
long long ggetdist(int xx,int yy,int zz,int xxx,int yyy,int zzz){
long long dist=1LL*(xx-xxx)*(xx-xxx)+1LL*(yy-yyy)*(yy-yyy)+1LL*(zz-zzz)*(zz-zzz);
return dist;
}
//bfs，为了反作弊，用了自己的名字缩写
int cgg(int cur){
q.init();
memset(vis,0,sizeof(vis));
q.gpush(cur);
vis[cur]=1;
while(q.f!=q.t){
int gg=q.gtop();
q.gpop();
for(unsigned int i=0;i<mapp[gg].size();i++){
if(tvis[mapp[gg][i]]){//这样判断比较方便
//如果遍历到了终点，就返回可以
return 1;
}
if(!vis[mapp[gg][i]]){
q.gpush(mapp[gg][i]);
vis[mapp[gg][i]]=1;
}
}
}
//没找到，返回不可以
return 0;
}
int main(){
freopen("cheese.in","r",stdin);
freopen("cheese.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&h,&r);
//读入点的数据
for(int i=0;i<n;i++){
scanf("%d%d%d",&indd[i][0],&indd[i][1],&indd[i][2]);
}
//接下来是一堆初始化，由于是多组数据，这非常重要。
memset(tvis,0,sizeof(tvis));
for(int i=0;i<n;i++){
mapp[i].clear();
}
s.clear();
sflag=0,tflag=0;//用于记录是否有终点和起点
for(int i=0;i<n;i++){
flag=0;//用于判断一个节点是否既是起点又是终点
if(indd[i][2]+r<=0||indd[i][2]-r>=h){
//排除一些无关的节点（即完全在奶酪外面）
continue;
}
if(indd[i][2]<=r&&indd[i][2]>-r){
//存起点
sflag=1;
s.push_back(i);
flag++;
}
if(indd[i][2]>=(h-r)&&indd[i][2]<(h+r)){
//存终点
tvis[i]=1;
tflag=1;
flag++;
}
if(flag==2){
//如果存在一个节点既是起点又是终点，那么就直接输出可以
printf("Yes\n");
break;
}
for(int j=i+1;j<n;j++){
//遍历当前节点是否与其他节点联通（建图）
if(ggetdist(indd[i][0],indd[i][1],indd[i][2],indd[j][0],indd[j][1],indd[j][2])<=1LL*4*r*r){
mapp[i].push_back(j);
mapp[j].push_back(i);
}
}
}
if(flag==2){
//代表问题已经解决
continue;
}
if(!tflag||!sflag){
//如果没有起点或是没有终点，显然不行
printf("No\n");
continue;
}
flag=0;//用于记录是否有解
//开始bfs
for(unsigned int i=0;i<s.size();i++){
//遍历每一个起点
if(cgg(s[i])){
//如果有解记录
flag=1;
break;
}
}
//输出结果
if(flag){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}

总结：真心不难，非常简单。