BYR Achieve · 镜像论坛

POJ2882 这道题过得好艰苦，MJ和主号加起来交了三十几次，还是没有最后搞懂。本题题意，要求在一个1到100的3D空间内放食物，每个食物占一格，给出一系列的食物摆放位置，问最后有几个空的空间（就像围棋中的规则一样，但这题是在3D的空间里下围棋）。这题有两种解法。先说容易想到的。用并查集。用一个三维数组存放这个放食物的空间，space[N][N][N]。初始值为0。注意，如果被放上食物的点的最大的坐标为max,则这个space[][][]就应该至少用到(max+2)*(max+2)*(max+2)的大小，即相当于在原有空间的外面又套上了一层膜（这是并查集统计的需要，否则答案错误）。然后按输入放食物的点的顺序把放上食物的点赋成1。等输入完了后，这个三维数组就成了一个由数字0和1构成的模拟空间，数组值为0表示此点为空，没有放上食物;为1表示此点放上了食物。接下来就是并查集操作了。遍历这个三维数组，对于每个没有放食物的点(i,j,k)，分别检查(i+1,j,k),(i,j+1,k)和(i,j,k+1)这三个方向上的点是不是也没被放上食物。如果这三个方向的点也没被放上食物，则合并(i,j,k)和三个相应的点。遍历了数组后，检查并查集中有多少个集合。设并查集中有count个集合，共有m个点被放上了食物，则最后答案应该是count-m-1。代码如下：注意代码中加注释的那行。用时：375MS。 #include<stdio.h> #include<iostream> #include<set> #define M 105 using namespace std; int space[M][M][M]; int Mfset[M*M*M],maxi,maxj,maxk; int root(int a) { if(Mfset[a]==a) return a; Mfset[a] = root(Mfset[a]); return Mfset[a]; } bool same(int a,int b) { return root(a)==root(b); } void merge(int a,int b) { if(same(a,b)) return ; Mfset[Mfset[a]]=Mfset[b]; } int value(int i,int j,int k) { return k*(maxi+2)*(maxj+2)+i*(maxj+2)+j+1; } int main() { int ncase,m,i,j,k,x,y,z,ans; scanf("%d",&ncase); while(ncase--) { scanf("%d",&m); for(i=0;i<M;i++) for(j=0;j<M;j++) for(k=0;k<M;k++) space[i][j][k]=1; maxi=maxj=maxk=0;/////////////大家的眼光看过来，看过来(maxi,maxj,maxk分别表示x,y,z方向上最大的坐标) for(i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); space[x][y][z]=0; if(x>maxi) maxi=x; if(y>maxj) maxj=y; if(z>maxk) maxk=z; } for(i=1;i<=(maxi+2)*(maxj+2)*(maxk+2);i++) Mfset[i]=i; for(i=0;i<=maxi+1;i++) for(j=0;j<=maxj+1;j++) for(k=0;k<=maxk+1;k++) { if(k+1<=maxk+1) if(space[i][j][k+1]!=0 && space[i][j][k]!=0) merge(value(i,j,k+1),value(i,j,k)); if(j+1<=maxj+1) if(space[i][j+1][k]!=0 && space[i][j][k]!=0) merge(value(i,j+1,k),value(i,j,k)); if(i+1<=maxi+1) if(space[i+1][j][k]!=0 && space[i][j][k]!=0) merge(value(i+1,j,k),value(i,j,k)); } for(i=1,ans=0;i<=(maxi+2)*(maxj+2)*(maxk+2);i++) if(Mfset[i]==i) ans++; printf("%d\n",ans-m-1); } return 0; } 理论上如果把加注释的那行改成maxi=maxj=maxk=-50;对结果应该不会有影响，但实践表明，如果把maxi，maxj，maxk的初值改成-2或者小于-2的数时，结果是WA，而把它们初始成0或者1时才会AC。现在说第二种做法。BFS。同样用一个space[][][]模拟放食物的空间，这一点和第一种做法一样，也需要在所用空间外面包一层膜。初始化空间后，就开始遍历整个三维数组。对于每个点，如果这个点没有被放上食物，则以这个点为起点，广度优先地遍历这个点所在的empy space。这个BFS过程就好像一个气球不断地膨胀，直到它遇到四周空间的障碍物才停下。每BFS一次，就相应地把这个被搜索的empy space填满，同时count++。（count的初始值为0，地球人都知道）。最后的答案的count-1。代码如下：同样注意加注释的那行。用时：500MS。 #include<stdio.h> #include<iostream> #include<queue> #define NN 150 using namespace std; struct node { int x,y,z; }; int space[NN][NN][NN],maxi,maxj,maxk; queue<node> qq; int main() { int ncase,m,i,j,k,x,y,z,ans,ti,tj,tk; node temp; scanf("%d",&ncase); while(ncase--) { scanf("%d",&m); for(i=0;i<NN;i++) for(j=0;j<NN;j++) for(k=0;k<NN;k++) space[i][j][k]=1; maxi=maxj=maxk=0;//////////看过来，看过来………… while(m--) { scanf("%d%d%d",&x,&y,&z); space[x][y][z]=0; if(x>maxi) maxi=x; if(y>maxj) maxj=y; if(z>maxk) maxk=z; } ans=0; for(i=0;i<=maxi+1;i++) for(j=0;j<=maxj+1;j++) for(k=0;k<=maxk+1;k++) { if(space[i][j][k]==0) continue; temp.x=i; temp.y=j; temp.z=k; qq.push(temp); space[temp.x][temp.y][temp.z]=0; while(!qq.empty()) { ti=qq.front().x; tj=qq.front().y; tk=qq.front().z; if(tk+1<=maxk+1 && space[ti][tj][tk+1]!=0) { temp.x=ti; temp.y=tj; temp.z=tk+1; qq.push(temp); space[temp.x][temp.y][temp.z]=0; } if(tk-1>=0 && space[ti][tj][tk-1]!=0) { temp.x=ti; temp.y=tj; temp.z=tk-1; qq.push(temp); space[temp.x][temp.y][temp.z]=0; } if(tj+1<=maxj+1 && space[ti][tj+1][tk]!=0) { temp.x=ti; temp.y=tj+1; temp.z=tk; qq.push(temp); space[temp.x][temp.y][temp.z]=0; } if(tj-1>=0 && space[ti][tj-1][tk]!=0) { temp.x=ti; temp.y=tj-1; temp.z=tk; qq.push(temp); space[temp.x][temp.y][temp.z]=0; } if(ti+1<=maxi+1 && space[ti+1][tj][tk]!=0) { temp.x=ti+1; temp.y=tj; temp.z=tk; qq.push(temp); space[temp.x][temp.y][temp.z]=0; } if(ti-1>=0 && space[ti-1][tj][tk]!=0) { temp.x=ti-1; temp.y=tj; temp.z=tk; qq.push(temp); space[temp.x][temp.y][temp.z]=0; } qq.pop(); } ans++; } printf("%d\n",ans-1); } return 0; } 加注释的原因和第一种方法中出现的问题相同。一旦它们被初始化成-2或者更小的数时，结果就是WA。这个问题我还没想明白，有待大家来解决。

[讨论]POJ2882解题报告