星区划分（并查集+枚举）

------------恢复内容开始------------

星区划分
时间限制: 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*-

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n,m;

struct nobe{
int x,y,z,v;
int root;
}a[maxn];

bool check(int i,int j){
if(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)+abs(a[i].z-a[j].z)<=1&&abs(a[i].v-a[j].v)<=m)
    return true;
return false;
}

int find(int k){
if(k!=a[k].root) a[k].root=find(a[k].root);
return a[k].root;
}

void Union(int i,int j){
i=find(i),j=find(j);
if(i!=j)
    a[i].root=j;
}

int main(){
int res=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
    cin>>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(j!=i){
    if(check(i,j))
        Union(i,j);
}
for(int i=0;i<=n;i++)
    if(a[i].root==i)
    res++;
cout<<res<<endl;
return 0;
}

原题（看一个博主发过，觉得很像）

题目描述
天文学家Doctor博士发明了一种太空分区方法，在这个方法中，宇宙里亮度相近的区域被划为同一个星区。空间中相邻两区域若亮度差不大于给定整数M，则这两区域属于同一星区。现给你一个空间的三维坐标图，每个坐标整点表示一个区域，其值表示其亮度，而其上、下、左、右、前、后六个区域被认为是与其相邻的。请你计算一下该空间内的星区数量。
输入
第一行三个正整数x、y、z（x、y、z<=50），表示空间的长宽高。
第二行一个整数M。
接下来为一行，x*y*z个0~255的整数，按照空间坐标大小的顺序由小到大依次给出每个区域的亮度。
说明：对于空间两点p1(x1,y1,z1)和p2(x2,y2,z2)，p1<p2当且仅当(x1<x2)或者(x1=x2且y1<y2)或者(x1=x2且y1=y2且z1<z2)。
输出
一个整数，空间中的星区数量。

我没看懂题，先码，不过感觉代码不对，check根本没用上

#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

------------恢复内容结束------------

原文链接: https://www.cnblogs.com/asunayi/p/12572939.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/376750

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

星区划分（并查集+枚举）

相关推荐