思路：将三维空间网格化，每个长方体占据的所有单元标记为1。求面积的话，DFS所有的单元，依次检查是上下左右前后六个方向上相邻单元是否为1，若否则是表面，面积加+1。求体积的话，从外面某个单元开始DFS，求出外面值为0的单元的个数，那么总单元个数 - 外部值为0的单元个数 = 雕塑体积。但是由于外部单元个数巨大会导致堆栈溢出，所以需要对坐标进行离散化，另外应选BFS。
原来vjudge 有时本地运行OK单提交就编译错误是因为 #include<bits/stdc++.h> 有的库可能与变量名冲突。
#includeusing namespace std;const int maxl = 30 + 5;const int maxn = 50 + 5;struct P{ int x0,y0,z0; P(int a0=0,int b0=0,int c0=0):x0(a0),y0(b0),z0(c0){}}Ps[maxn];int T,n,volu,area;int x0,y0,z0,x,y,z;int V[maxl][maxl][maxl];void process(){ for(int i = 0;i < x;i++){ for(int j = 0;j < y;j++){ for(int k = 0;k < z;k++){ V[x0+i][y0+j][z0+k] = 1; } } }}void dfs1(int x,int y,int z){ volu++; V[x][y][z] = -1; for(int dx = -1;dx <= 1;dx++){ for(int dy = -1;dy <= 1;dy++){ for(int dz = -1;dz <= 1;dz++){ if(!dx && !dy && !dz) continue; if(x+dx >= 0 && x+dx = 0 && y+dy < maxl && z+dz >= 0 && z+dz < maxl && !V[x+dx][y+dy][z+dz]){ dfs1(x+dx,y+dy,z+dz); } } } }}void dfs2(int x,int y,int z){ V[x][y][z] = -2; if(V[x][y][z+1] == -1) area++; if(V[x][y][z-1] == -1) area++; if(V[x][y+1][z] == -1) area++; if(V[x][y-1][z] == -1) area++; if(V[x+1][y][z] == -1) area++; if(V[x-1][y][z] == -1) area++; for(int dx = -1;dx <= 1;dx++){ for(int dy = -1;dy <= 1;dy++){ for(int dz = -1;dz <= 1;dz++){ if(V[x+dx][y+dy][z+dz] == 1){ dfs2(x+dx,y+dy,z+dz); } } } }}int main(){ // freopen("data.in","r",stdin); // freopen("data.out","w",stdout); scanf("%d",&T); while(T--){ scanf("%d",&n); volu = area = 0; memset(V,0,sizeof(V)); for(int i = 0;i < n;i++){ scanf("%d%d%d%d%d%d",&x0,&y0,&z0,&x,&y,&z); Ps[i] = P(x0,y0,z0); process(); } dfs1(0,0,0); for(int i = 0;i < n;i++){ P t = Ps[i]; if(V[t.x0][t.y0][t.z0] == 1) dfs2(t.x0,t.y0,t.z0); } printf("%d %d\n",area,maxl*maxl*maxl - volu); } return 0;}
AC代码：
#includeusing namespace std;const int maxn = 100 + 5;const int maxc = 1000 + 5;int T,n,area,volume,nx,ny,nz;int x0[maxn],y0[maxn],z0[maxn],x1[maxn],y1[maxn],z1[maxn];int xs[maxn],ys[maxn],zs[maxn];int dx[] = { -1,1, 0,0, 0,0 };int dy[] = { 0,0,-1,1, 0,0 };int dz[] = { 0,0, 0,0,-1,1 };int visit[maxn][maxn][maxn];struct Cell{ int x,y,z; Cell(int x = 0,int y = 0,int z = 0):x(x),y(y),z(z){}; void setVis(){ visit[x][y][z] = -1; } int inside(){ return x >= 0 && x < nx-1 && y >= 0 && y < ny-1 && z >= 0 && z < nz-1; } int visited(){ return visit[x][y][z] == -1; } int Solid(){ return visit[x][y][z] == 1; } Cell near(int i){ return Cell(x + dx[i],y + dy[i],z + dz[i]); } int volume(){ return (xs[x+1]-xs[x])*(ys[y+1]-ys[y])*(zs[z+1]-zs[z]); } int area(int i){ if(dx[i]) return (ys[y+1]-ys[y])*(zs[z+1]-zs[z]); else if(dy[i]) return (xs[x+1]-xs[x])*(zs[z+1]-zs[z]); else return (xs[x+1]-xs[x])*(ys[y+1]-ys[y]); }};void floodFill(){ Cell c; c.setVis(); queue q; q.push(c); while(!q.empty()){ Cell c = q.front(); q.pop(); volume += c.volume(); for(int i = 0;i < 6;i++){ Cell c2 = c.near(i); if(!c2.inside()) continue; if(c2.Solid()) area += c.area(i); else if(!c2.visited()){ c2.setVis(); q.push(c2); } } } volume = maxc*maxc*maxc - volume;}void discrete(int a[],int & n){ sort(a,a + n); n = unique(a,a + n) - a;}int pos(int a[],int n,int x){ return lower_bound(a,a + n,x) - a;}int main(){ // freopen("data.in","r",stdin); // freopen("data.out","w",stdout); scanf("%d",&T); while(T--){ scanf("%d",&n); nx = ny = nz = 2; xs[0] = ys[0] = zs[0] = 0; xs[1] = ys[1] = zs[1] = maxc; for(int i = 0;i < n;i++){ scanf("%d%d%d%d%d%d",&x0[i],&y0[i],&z0[i],&x1[i],&y1[i],&z1[i]); x1[i] += x0[i]; y1[i] += y0[i]; z1[i] += z0[i]; xs[nx++] = x0[i]; xs[nx++] = x1[i]; ys[ny++] = y0[i]; ys[ny++] = y1[i]; zs[nz++] = z0[i]; zs[nz++] = z1[i]; } discrete(xs,nx); discrete(ys,ny); discrete(zs,nz); memset(visit,0,sizeof(visit)); for(int i = 0;i < n;i++){ int sx = pos(xs,nx,x0[i]); int ex = pos(xs,nx,x1[i]); int sy = pos(ys,ny,y0[i]); int ey = pos(ys,ny,y1[i]); int sz = pos(zs,nz,z0[i]); int ez = pos(zs,nz,z1[i]); for(int j = sx;j < ex;j++){ for(int k = sy;k < ey;k++){ for(int l = sz;l < ez;l++){ visit[j][k][l] = 1; } } } } area = volume = 0; floodFill(); printf("%d %d\n",area,volume); } return 0;} |