题目链接:https://vjudge.net/problem/UVA-12171
题目大意:给你若干长方体,让你统计这些长方体的体积和外表面积,需要注意的是,不是统计长方体实际所占据的体积,因为这些长方体组合之后可能会形成一个封闭的区域,这个封闭区域的体积也需要被计算在内的
解决方法:直接算太麻烦,因为要考虑封闭区域,而封闭区域可能还产生嵌套,所以不能直接算,可以通过给这些长方体外围加上一圈空气,这样我们可以使用flood fill算法计算出空气的体积,同时也可以计算出外表面积,然后间接算出体积,另外还有一个问题,那就是题目中所给坐标的范围是1-500,如果我们拿一个3维数组去存储的话,需要500*500*500=1.25亿个int类型数的存储空间,换成char类型也存不下,所以考虑离散化进行压缩
//代码是参考别人的
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=55;
const int maxc=1001;
//用来存储原始坐标数据
int x0[maxn],y0[maxn],z0[maxn],x1[maxn],y1[maxn],z1[maxn];
//存储离散坐标个数和数据
int nx,ny,nz;
int xs[maxn*2],ys[maxn*2],zs[maxn*2];
//color是用于辨别三维网格是否为实心,在floodfill时也用于标记是否访问过
int color[maxn*2][maxn*2][maxn*2];
//用于当前网格的六个方向的移动
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
/*创建网格数据结构
*x,y,z个网格在离散坐标数组中的位置而不是原始坐标
*/
struct Cell{
int x, y, z;
Cell(int x=0,int y=0,int z=0):x(x),y(y),z(z){}
//判断网格是否越界
bool inside(){
return x>=0&&x<nx-1&&y>=0&&y<ny-1&&z>=0&&z<nz-1;
}
//判断是否为实心,即是否为雕塑的组成部分
bool solid(){
return color[x][y][z]==1;
}
//是否访问过
bool visited(){
return color[x][y][z]==2;
}
//标记为访问过
void setVis(){
color[x][y][z]=2;
}
//向相邻的网格移动,dir代表移动方向
Cell near(int dir){
return Cell(x+dx[dir], y+dy[dir], z+dz[dir]);
}
//计算该网格的原始体积并返回
int volume(){
return (xs[x+1]-xs[x])*(ys[y+1]-ys[y])*(zs[z+1]-zs[z]);
}
//计算该网格的表面积并返回
int area(int dir){
if(dx[dir]) return (ys[y+1]-ys[y])*(zs[z+1]-zs[z]); //如果dx[dir]不为零说明是从x方向移过来的,而我们是从空气中移动的,所以该X方向的面在表面
else if(dy[dir]) return (xs[x+1]-xs[x])*(zs[z+1]-zs[z]); //同上
return (xs[x+1]-xs[x])*(ys[y+1]-ys[y]); //同上
}
};
//离散函数
void discretize(int* x, int& n) {
sort(x, x+n);
n = unique(x, x+n) - x;
}
//寻找x0在离散坐标数组中的位置
int pos(int* x, int n, int x0) {
return lower_bound(x, x + n, x0) - x;
}
//搜索对空气网格进行
void floodfill(int &v, int &s){
v = s = 0;
Cell c;
queue<Cell> q;
c.setVis();
q.push(c);
while(!q.empty()){
Cell c1=q.front(); q.pop();
v+=c1.volume();
for(int i=0;i<6;++i){
Cell c2=c1.near(i);
if(!c2.inside()) continue;
if(c2.solid()) s+=c1.area(i); //如果这个方向的是实心网格则记入表面积
else if(!c2.visited()){ //如果不是则空气,加入队列进行搜索
c2.setVis();
q.push(c2);
}
}
}
v = maxc*maxc*maxc - v;
}
int main(){
// freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);
while(T--){
int n;
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];
}
discretize(xs, nx);
discretize(ys, ny);
discretize(zs, nz);
memset(color, 0, sizeof(color));
//将雕塑的组成不封染成solid实心
for(int i=0;i<n;++i){
int sx=pos(xs, nx,x0[i]), ex=pos(xs, nx, x1[i]);
int sy=pos(ys, ny,y0[i]), ey=pos(ys, ny, y1[i]);
int sz=pos(zs, nz,z0[i]), 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){
color[j][k][l]=1;
}
}
}
}
int v, s;
floodfill(v, s);
printf("%d %d\n", s, v);
}
return 0;
}