北京好一点的微网站开发公司,一家只做家纺的网站,出版社网站建设方案,谷歌收录wordpress我天#xff01;哥们经过两个周的忙碌又重生了#xff01;
原题链接#xff1a;528. 奶酪 - AcWing题库
本题注意点#xff1a;
注意几个边界值#xff0c;如果说没有球连接顶部或者底部#xff0c;老鼠是不可能上来的#xff0c;直接say no!要利用公式判断两个球是相…我天哥们经过两个周的忙碌又重生了
原题链接528. 奶酪 - AcWing题库
本题注意点
注意几个边界值如果说没有球连接顶部或者底部老鼠是不可能上来的直接say no!要利用公式判断两个球是相切or相交 相离是没有可能的也是直接say no主要距离公式 d i s t ( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 ( z 1 − z 2 ) 2 {dist} \sqrt{ (x_1 - x_2)^2 (y_1 - y_2)^2 (z_1 - z_2)^2 } dist(x1−x2)2(y1−y2)2(z1−z2)2
看题目的大意有点像查找最小连通图的影子现在先用并查集解决问题
解法1并查集
时间复杂度 T ( n 2 ) T(n^2) T(n2)运行时间753ms
AC代码:
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N1010;int t;
int p[N];
int n,h,r;struct Spot{ll x,y,z;
}a[N];int find(int x){if(p[x]!x) {p[x]find(p[x]);}return p[x];
}int judge(ll x1,ll x2,ll y1,ll y2,ll z1,ll z2,ll r)//判断两个空洞是否有交集
{return (x1-x2)*(x1-x2)(y1-y2)*(y1-y2)(z1-z2)*(z1-z2)(4*r*r)?1:0;
}void merge(int x,int y){p[find(x)]find(y);
}
int main()
{scanf(%d,t);while(t--){scanf(%d%d%d,n,h,r);for(int i1;in;i){a[i].xa[i].ya[i].z0; //一定要清空数组p[i]i; //并查集初始化}//0代表奶酪底部1001代表奶酪顶部p[0]0,p[1001]1001;for(int i1;in;i){cina[i].xa[i].ya[i].z;if(a[i].z-r0){ //空洞最低点在奶酪外或与奶酪相切与底部合并merge(i,0);}if(a[i].zrh){//同理最高点在奶酪外或相切与顶部合并merge(i,1001);}}for(int i1;in;i){for(int ji1;jn;j){if(judge(a[i].x,a[j].x,a[i].y,a[j].y,a[i].z,a[j].z,r)){//有交集就合并merge(i,j);}}}if(find(0)find(1001)) printf(Yes\n);//底部和顶部相连通即根节点相同else printf(No\n);}return 0;
}
解法2dfs(深度优先搜索)
主要思想用空间换取时间
AC 代码
//利用dfs
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N1010;int t;
int vis[N];
int found; //用于插眼
int n,h,r;struct Spot{ll x,y,z;
}a[N];int judge(ll x1,ll x2,ll y1,ll y2,ll z1,ll z2,ll r){return (x1-x2)*(x1-x2)(y1-y2)*(y1-y2)(z1-z2)*(z1-z2)(4*r*r)?1:0;
}
void dfs(int m){if(a[m].zrh){//递归出口即搜到顶端found1;return;}vis[m]1;//标记走过for(int i1;in;i){if(!vis[i]judge(a[i].x,a[m].x,a[i].y,a[m].y,a[i].z,a[m].z,r)){//没有访问且两个空洞有交集继续搜索dfs(i);}}
}
int main(){cint;while(t--){found0; //初始化for(int i1;in;i){a[i].xa[i].ya[i].z0; //一定要清空数组}memset(vis,0,sizeof(vis));cinnhr;for(int i1;in;i){cina[i].xa[i].ya[i].z;}for(int i1;in;i){if(!vis[i]a[i].zr){//没有访问过并且和底部相连通即dfs入口dfs(i);}if(found1)break;}if(found1) printf(Yes\n);else printf(No\n);}return 0;
}
