hiho151周*

题目链接

题目大意：依次在给定的三维坐标上垒方块，对于一个新的坐标需满足两个条件

1：六个方向有相邻的方块或者z==1【题目说明了初始状态是：所有z==0的位置都有方块】

2：该位置存在一条到无穷远处的路径，即不能被已有的方块包围。

给定一个序列，问按照这个序列放置方块会不会违反上述两条规则。

1<=x,y,z<=100 N<=100000

-----------------------------------------------------------------------------------------------------

条件一容易判断。

条件二如果正序处理，则每来一个坐标都需要判断和无穷远处的连通性，复杂度很大。

则反过来处理，首先把空格子合并，分到几个集合里。然后倒着删方块，每删一个方块，就merge一下该

方块及周围的六个空格子，merge完后判断方块所在格子是否和无穷远处联通

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <cmath>

#include <vector>

#include <string>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define MAX(a,b) ((a)>=(b)?(a):(b))

#define MIN(a,b) ((a)<=(b)?(a):(b))

#define OO 0x0fffffff

using namespace std;

const int N = ;

bool tag[N][N][N];

int father[N*N*N];

int ids[N][N][N];

int xs[],ys[],zs[];

int maxx,maxy,maxz;

int minx,miny,minz;

const int dir[][] = {{,,},{,,-},{,,},{,-,},{,,},{-,,}};

bool judge(int x,int y,int z){

    if(z==) return false;

    if(x<minx) return false;

    if(x>maxx) return false;

    if(y<miny) return false;

    if(y>maxy) return false;

    if(z<minz) return false;

    if(z>maxz) return false;

    return true;

}

int find(int id){

    int fid = father[id];

    if(fid==id) return fid;

    return (father[id]=find(fid));

}

void merge(int a,int b){

    int fa = find(a);

    int fb = find(b);

    if(fa==fb) return ;

    father[fb] = fa;

}

int main(){

    int n,t;

    for(int i=;i<;i++) for(int j=;j<;j++) for(int k=;k<;k++){

        ids[i][j][k] = i*+j*+k;

    }

    for(scanf("%d",&t);t--;){

        cin>>n;

        memset(tag,false,sizeof(tag));

        bool flag = true;

        maxx=maxy=maxz=-OO;

        minx=miny=minz=OO;

        for(int i=;i<n;i++){

            scanf("%d%d%d",xs+i,ys+i,zs+i);

            maxx=MAX(maxx,xs[i]);maxy=MAX(maxy,ys[i]);maxz=MAX(maxz,zs[i]);

            minx=MIN(minx,xs[i]);miny=MIN(miny,ys[i]);minz=MIN(minz,zs[i]);

            if(tag[xs[i]][ys[i]][zs[i]]) flag = false;

            else if(zs[i]==){

                tag[xs[i]][ys[i]][zs[i]] = true;

            }

            else{

                for(int d=;d<;d++){

                    int tx = xs[i]+dir[d][];

                    int ty = ys[i]+dir[d][];

                    int tz = zs[i]+dir[d][];

                    if(tag[tx][ty][tz]){

                        tag[xs[i]][ys[i]][zs[i]] = true;

                        break;

                    }

                }

                if(!tag[xs[i]][ys[i]][zs[i]]) flag = false;

            }

        }

        if(!flag) puts("No");

        else{

            minx--;miny--;minz--;

            maxx++;maxy++;maxz++;

            for(int id=ids[minx][miny][minz];id<=ids[maxx][maxy][maxz];id++) father[id] = id;

            for(int i=minx;i<=maxx;i++)

            for(int j=miny;j<=maxy;j++)

            for(int k=minz;k<=maxz;k++){

                if((k!=)&&(!tag[i][j][k])){

                    for(int d=;d<;d++){

                        int ti = i+dir[d][];

                        int tj = j+dir[d][];

                        int tk = k+dir[d][];

                        if(judge(ti,tj,tk)&&(!tag[ti][tj][tk])){

                            merge(ids[i][j][k],ids[ti][tj][tk]);

                        }

                    }

                }

            }

            int ancestor = ids[maxx][maxy][maxz];

            for(int i=n-;i>=;i--){

                if(!flag) break;

                int curId = ids[xs[i]][ys[i]][zs[i]];

                for(int d=;d<;d++){

                     int tx = xs[i]+dir[d][];

                     int ty = ys[i]+dir[d][];

                     int tz = zs[i]+dir[d][];

                     if(judge(tx,ty,tz)&&(!tag[tx][ty][tz])){

                        merge(curId,ids[tx][ty][tz]);

                     }

                }

                if(find(curId)!=find(ancestor)){

                    flag = false;

                }

                else{

                    tag[xs[i]][ys[i]][zs[i]]=false;

                }

            }

            if(!flag) puts("No");

            else puts("Yes");

        }

    }

    return ;

}

巴特西

hiho151周*

最新文章

热门文章