数据结构王歧--P3958 奶酪--题解
程序员文章站
2024-01-11 15:19:58
...
P3958奶酪题解
题目截图
题目解答
题目主要运用深度优先搜索算法
#include<bits/stdc++.h>
using namespace std;
struct point
{
int x;
int y;
int z;
};
struct point p[1005];//记录点坐标
int n;//奶酪空洞数量
long long h,r;//奶酪高度及球形空洞半径
int g[1005][1005];//记录两点之间能否连通,能,记录1;否,记录0
int visit[1005];//记录点是否被访问过
/*读入数据*/
void readdata()
{
int i;
cin>>n>>h>>r;
for(i=0;i<n;i++)
{
cin>>p[i].x>>p[i].y>>p[i].z;
}
}
/*初始化*/
void init()
{
int i,j;
long long dx,dy,dz;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
dx=p[i].x-p[j].x;
dy=p[i].y-p[j].y;
dz=p[i].z-p[j].z;
if(dx*dx+dy*dy+dz*dz<=4*r*r)
g[i][j]=1;
else g[i][j]=0;
}
}
for(i=0;i<n;i++) visit[i]=0;//最初标记为全部未访问
}
/*深搜*/
void dfs(int target)
{
//起点start,终点target
int start;
visit[target]=1;//标记这次搜索终点已经访问
for(start=0;start<n;start++)
{
//如果本次搜索起点与终点间能连通且起点还没有访问
if(g[target][start]==1&&visit[start]==0)
{
//就从这个点继续
dfs(start);
}
}
}
/*主函数*/
int main()
{
int flag;
int t,i,j;
cin>>t;
while(t--)
{
readdata();
init();
for(i=0;i<n;i++)
{
if(p[i].z<=r&&visit[i]==0)
dfs(i);
}
flag=0;
for(i=0;i<n;i++)
{
if(p[i].z+r>=h&&visit[i]==1)
{
flag=1;
break;
}
}
if(flag==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
上一篇: [DFS] [洛谷] P1433 吃奶酪
下一篇: 总结关于swiper组件注意点