天空黑暗到一定程度，星辰就会熠熠生辉
星区划分
时间限制: 1 Sec 内存限制: 128 MB
提交: 1056 解决: 237
[状态] [提交] [命题人:外部导入]
题目描述
爱好天文的小七发明了一种太空分区方法，在这个方法中，宇宙里亮度相近的星星被划为同一个星区。空间中任意相邻或坐标相同的星星若亮度差不大于给定整数M，则这两个星星属于同一星区(两个星星可能会有相同的坐标）。
现给你一个空间n个星星的三维坐标(x,y,z)，和亮度值v，每个星星的上、下、左、右、前、后的六个相邻位置被认为是与其相邻的。请你计算一下该空间内的星区数量。
输入
第一行1个正整数n。n<=1000
第二行 1个正整数m。m<=109
第二行到第n+1行，每行四个正整数x,y,z,v。0<=x,y,z,v<=109
输出
一行正整数k，代表星区数量。
样例输入 Copy
5
2
1 1 1 2
1 2 3 2
1 2 2 5
1 1 0 3
1 0 1 3
样例输出 Copy
3
思路:
暴力枚举每个点，判断周围六个点以及本身是否能够与他构成一个星区，如果可以构成同一星区但不在同一星区，要合并。
（ 比赛的时候思路到这里就卡了，身为一名数据结构选手竟然没想到用并查集来维护。）
暴力枚举每一颗星星，然后搜索它的六个方向坐标和与自己相同坐标的亮度，亮度合
法的话就用并查集把他们的祖先统一，最后统计一下祖先是自己的数量就是星区的数量。
复杂度：1000 * 1000 * 7
代码:
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; struct node{ int x,y,z,v; int root; }a[maxn]; int n,m; bool check(int i,int j){ int x1=a[i].x,x2=a[j].x; int y1=a[i].y,y2=a[j].y; int z1=a[i].z,z2=a[j].z; int w1=a[i].v,w2=a[j].v; if(x1==x2+1&&y1==y2&&z1==z2||x1==x2-1&&y1==y2&&z1==z2||x1==x2&&y1==y2+1&&z1==z2||x1==x2&&y1==y2-1&&z1==z2||x1==x2&&y1==y2&&z1==z2+1||x1==x2&&y1==y2&&z1==z2-1||x1==x2&&y1==y2&&z1==z2) if(abs(w1-w2)<=m) return true; return false; } int Find(int x){ if(x!=a[x].root) a[x].root=Find(a[x].root); return a[x].root; } void Union(int x,int y){ x=Find(x),y=Find(y); if(x!=y){ a[x].root=y; } } int main(){ /// int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d%d%d%d",&a[i].x,&a[i].y, &a[i].z ,&a[i].v ); a[i].root=i; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) continue; else if(check(i,j)) Union(i,j); int res=0; for(int i=1;i<=n;i++) //cout<<a[i].root<<" "; if(a[i].root==i) res++; printf("%d\n",res); return 0; }
最后放一个类似的题叭，应该是未改过的题~
题目描述
天文学家Doctor博士发明了一种太空分区方法，在这个方法中，宇宙里亮度相近的区域被划为同一个星区。空间中相邻两区域若亮度差不大于给定整数M，则这两区域属于同一星区。现给你一个空间的三维坐标图，每个坐标整点表示一个区域，其值表示其亮度，而其上、下、左、右、前、后六个区域被认为是与其相邻的。请你计算一下该空间内的星区数量。
输入
第一行三个正整数x、y、z（x、y、z<=50），表示空间的长宽高。
第二行一个整数M。
接下来为一行，xyz个0~255的整数，按照空间坐标大小的顺序由小到大依次给出每个区域的亮度。
说明：对于空间两点p1(x1,y1,z1)和p2(x2,y2,z2)，p1<p2当且仅当(x1<x2)或者(x1=x2且y1<y2)或者(x1=x2且y1=y2且z1<z2)。
输出
一个整数，空间中的星区数量。
这个直接dfs就可以，因为坐标都是连续的，而且数据范围也比较小。
#include <bits/stdc++.h> #define ll long long using namespace std; int num[55][55][55]; bool mp[55][55][55]; int d; int n,m,h; int dx[]={0,0,-1,1,0,0}; int dy[]={1,-1,0,0,0,0}; int dz[]={0,0,0,0,1,-1}; bool check(int x,int y,int z) { if(x<1||x>n||y<1||y>m||z<1||z>h) return 1; if(mp[x][y][z]) return 1; return 0; } void dfs(int x,int y,int z,int p){ mp[x][y][z]=true; for(int i=0; i<6; ++i){ int next_x=x+dx[i]; int next_y=y+dy[i]; int next_z=z+dz[i]; if(next_x>=1&&next_x<=n&&next_y>=1&&next_y<=m&&next_z>=1&&next_z<=h&&!mp[next_x][next_y][next_z]&&abs(num[next_x][next_y][next_z]-p)<=d) { dfs(next_x,next_y,next_z,num[next_x][next_y][next_z]); } } } int main(){ scanf("%d%d%d%d",&n,&m,&h,&d); for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ for(int k=1;k<=h;++k){ scanf("%d",&num[i][j][k]); } } } int ent=0; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ for(int k=1;k<=h;++k){ if(!mp[i][j][k]){ ent++; dfs(i,j,k,num[i][j][k]); } } } } printf("%d\n",ent); return 0; } //出自：Dili_iiii
参考博客：【dfs模板】dfs找联通块分区 - Dili_iiii - 博客园
其实这场比赛打的挺自闭的，好几个人讨论这个题也没想到并查集，最后想到的时候不想写了。但是真的嘴上说着不想打了，却还是满腔热血的去vj拉题，这也许就是acm的魅力所在吧。
