欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构王歧--P3958 奶酪--题解

程序员文章站 2024-01-11 15:19:58
...

P3958奶酪题解

题目截图

数据结构王歧--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;
}
相关标签: 数据结构 c++