难点: 理解离散化
这个题目中构造一个长宽高都为1001的容器,然后离散化 分割为多个小方块 (离散化:将这一方块用一个坐标表示),每个方块要么是实心,要么是空心。
通过lower_bound函数找到unique去重后的数组下标去三维遍历标记实心,然后bfs。
在这里,每一个方块的表示仅通过离散化后的单一坐标,与题目表示方法相同。
表面积计算通过bfs方向来源来判断哪一面。
空方块体积直接算,实心的不会进入bfs队列。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=50+1;
const int maxc=1000+1;
int xi[maxn],yi[maxn],zi[maxn],xi0[maxn],yi0[maxn],zi0[maxn],xl[maxn*2],yl[maxn*2],zl[maxn*2];
int nx,ny,nz,color[maxn*2][maxn*2][maxn*2];
int dx[]={1,-1,0,0,0,0},
dy[]={0,0,1,-1,0,0},
dz[]={0,0,0,0,1,-1};
struct loc{
int x,y,z;
loc(int x=0,int y=0,int z=0):x(x),y(y),z(z){}
bool valid()
{
return x>=0&&x<nx-1&&y>=0&&y<ny-1&&z>=0&&z<nz-1;
}
int volume()
{
return (xl[x+1]-xl[x])*(yl[y+1]-yl[y])*(zl[z+1]-zl[z]);
}
void setvis()
{
color[x][y][z]=2;
}
loc neighbor(int i)
{
return loc(x+dx[i],y+dy[i],z+dz[i]);
}
};
void filled(int &s,int& v)
{
v=s=0;
queue<loc>q;
q.push(loc(0,0,0));
color[0][0][0]=2;
while(!q.empty())
{
loc temp=q.front();q.pop();
v+=temp.volume();
for(int i=0;i<6;i++)
{
loc n=temp.neighbor(i);
if(!n.valid())continue;
if(!color[n.x][n.y][n.z]){n.setvis();q.push(n);}
else if(color[n.x][n.y][n.z]==2)continue;
else if(color[n.x][n.y][n.z]==1) //计算表面积
{
if(i<2) s+=(yl[n.y+1]-yl[n.y])*(zl[n.z+1]-zl[n.z]);
else if(i>3) s+=(yl[n.y+1]-yl[n.y])*(xl[n.x+1]-xl[n.x]);
else s+=(zl[n.z+1]-zl[n.z])*(xl[n.x+1]-xl[n.x]);
}
}
}
v=maxc*maxc*maxc-v;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,t,s,v;
cin>>t;
while(t--)
{
memset(color,0,sizeof(color));
xl[0]=yl[0]=zl[0]=0;
xl[1]=yl[1]=zl[1]=maxc;
nx=ny=nz=2;
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d%d%d%d%d%d",&xi[i],&yi[i],&zi[i],&xi0[i],&yi0[i],&zi0[i]);
//xi等为初始坐标,xi0等为长度
xl[nx++]=xi[i];xl[nx++]=xi[i]+xi0[i];
yl[ny++]=yi[i];yl[ny++]=yi[i]+yi0[i];
zl[nz++]=zi[i];zl[nz++]=zi[i]+zi0[i];
}
sort(xl,xl+nx);nx=unique(xl,xl+nx)-xl;
sort(yl,yl+ny);ny=unique(yl,yl+ny)-yl;
sort(zl,zl+nz);nz=unique(zl,zl+nz)-zl;
for(int i=0;i<n;i++)
{
int X1,Y1,Z1,X0,Y0,Z0;
X0=lower_bound(xl,xl+nx,xi[i])-xl;
Y0=lower_bound(yl,yl+ny,yi[i])-yl;
Z0=lower_bound(zl,zl+nz,zi[i])-zl;
X1=lower_bound(xl,xl+nx,xi[i]+xi0[i])-xl;
Y1=lower_bound(yl,yl+ny,yi[i]+yi0[i])-yl;
Z1=lower_bound(zl,zl+nz,zi[i]+zi0[i])-zl;
for(int X=X0;X<X1;X++)
for(int Y=Y0;Y<Y1;Y++)
for(int Z=Z0;Z<Z1;Z++)
color[X][Y][Z]=1;
}
filled(s,v);
cout<<s<<" "<<v<<endl;
}
return 0;
}