赞
踩
题目主要运用深度优先搜索算法
#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; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。