题意：某雕塑由n（n<=50)个长方体组成，长方体6个参数（x，y，z，w，d，h）均为1~500的整数，长方体可以镶嵌，并可以形成封闭空间，求该雕塑的表面积和体积，封闭空间也看作是雕塑的一部分
把雕塑放到坐标系中，对雕塑外的空气进行floodfill，可得到空气的内表面积和体积，内表面积即雕塑的表面积，坐标系下总体积减去空气体积即雕塑体积
但是以单位长度为基础的坐标系为500*500*500的网格，数组开不下，因为最多只有50个长方体，离散化后每个维度最多只有100个坐标间隔
因此可以进行离散化，网格只用开到100*100*100，记录每个网格各边的长度，在计算时用原来的长度
做题中：
错误1： floodfill 网格的移动使用了三个维度变化量-1,0,1的全组合，进入了雕塑的内部，实际上只进行六个正方向的填充
错误2：像floodfill这种不注重搜索深度和广度区别的算法用dfs和bfs都能实现，而本题用dfs会爆栈，最好使用bfs
// dfs /*#include<bits/stdc++.h> using namespace std; const int maxn=60; int anss,airv,ansv; struct cube{int x,y,z,w,d,h;int lx,ly,lz; } a[maxn];const int dx[10]={1,-1, 0, 0, 0, 0}; const int dy[10]={0, 0, 1,-1, 0, 0}; const int dz[10]={0, 0, 0, 0, 1,-1}; int pic[110][110][110]; int xyz[3][maxn*2],lxyz[3][maxn*2],lx,ly,lz; void fillcube(cube c){int px1,px2,py1,py2,pz1,pz2;for(int j=0;j<lx;j++){if(c.x==xyz[0][j])px1=j;if(c.x+c.w==xyz[0][j]){px2=j; break;}}for(int j=0;j<ly;j++){if(c.y==xyz[1][j])py1=j;if(c.y+c.d==xyz[1][j]){py2=j; break;}}for(int j=0;j<lz;j++){if(c.z==xyz[2][j])pz1=j;if(c.z+c.h==xyz[2][j]){pz2=j; break;}}for(int i=px1;i<px2;i++)for(int j=py1;j<py2;j++)for(int k=pz1;k<pz2;k++)pic[i+1][j+1][k+1]=1;} int cnt=0; void fillflood(int x,int y,int z){ // cout<<"HERE"<<endl;// printf("x %d y %d z %d %d\n",x,y,z,++cnt);pic[x][y][z]=2;if(x&&y&&z&&x!=lx&&y!=ly&&z!=lz)airv+=lxyz[0][x-1]*lxyz[1][y-1]*lxyz[2][z-1];//printf("x%d %d y%d %d z%d %d\n",x,y,z,lxyz[0][x-1],lxyz[1][y-1],lxyz[2][z-1]);int xi,yi,zi;for(int i=0;i<6;i++){xi=x+dx[i]; yi=y+dy[i]; zi=z+dz[i];if(xi>=0&&xi<lx+1&&yi>=0&&yi<ly+1&&zi>=0&&zi<lz+1){if(!pic[xi][yi][zi])fillflood(xi,yi,zi);else if(pic[xi][yi][zi]==1){// printf("x %d y %d z %d %d\n",x,y,z,++cnt); if(xi!=x)anss+=lxyz[1][y-1]*lxyz[2][z-1];if(yi!=y)anss+=lxyz[0][x-1]*lxyz[2][z-1];if(zi!=z)anss+=lxyz[0][x-1]*lxyz[1][y-1];// printf("%d\n",anss); } } } }int main(){int m,n;scanf("%d",&m);while(m--){memset(pic,0,sizeof(pic));anss=0; airv=0; scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d%d%d%d%d",&a[i].x,&a[i].y,&a[i].z,&a[i].w,&a[i].d,&a[i].h);xyz[0][2*i]=a[i].x; xyz[0][2*i+1]=a[i].x+a[i].w;xyz[1][2*i]=a[i].y; xyz[1][2*i+1]=a[i].y+a[i].d;xyz[2][2*i]=a[i].z; xyz[2][2*i+1]=a[i].z+a[i].h;}sort(xyz[0],xyz[0]+2*n); //xyz三向离散化 sort(xyz[1],xyz[1]+2*n);sort(xyz[2],xyz[2]+2*n);lx=unique(xyz[0],xyz[0]+2*n)-xyz[0]; //xyz三向离散化 ly=unique(xyz[1],xyz[1]+2*n)-xyz[1];lz=unique(xyz[2],xyz[2]+2*n)-xyz[2];ansv=(xyz[0][lx-1]-xyz[0][0])*(xyz[1][ly-1]-xyz[1][0])*(xyz[2][lz-1]-xyz[2][0]); // cout<<"v "<<ansv<<endl;for(int i=0;i<lx-1;i++){ //计算离散程度 lxyz[0][i]=xyz[0][i+1]-xyz[0][i]; }for(int i=0;i<ly-1;i++){ lxyz[1][i]=xyz[1][i+1]-xyz[1][i]; }for(int i=0;i<lz-1;i++){ lxyz[2][i]=xyz[2][i+1]-xyz[2][i]; }for(int i=0;i<n;i++) fillcube(a[i]);fillflood(0,0,0);ansv-=airv;printf("%d %d\n",anss,ansv);}return 0; }*/ //未知错误wa，应该是爆栈了，用bfs //new~ wa是因为floodfill 错了，不带斜连块，只有正xyz方向连块 // 改后过了uva ，不过 udebug上有一组50个的数据过不了，因该是爆栈了 // 再用bfs #include<bits/stdc++.h> using namespace std; const int maxn=60; int anss,airv,ansv; struct cube{int x,y,z,w,d,h;int lx,ly,lz; } a[maxn]; queue <int> qx,qy,qz; const int dx[10]={1,-1, 0, 0, 0, 0}; const int dy[10]={0, 0, 1,-1, 0, 0}; const int dz[10]={0, 0, 0, 0, 1,-1}; int pic[110][110][110]; int xyz[3][maxn*2],lxyz[3][maxn*2],lx,ly,lz; void fillcube(cube c){int px1,px2,py1,py2,pz1,pz2;for(int j=0;j<lx;j++){if(c.x==xyz[0][j])px1=j;if(c.x+c.w==xyz[0][j]){px2=j; break;}}for(int j=0;j<ly;j++){if(c.y==xyz[1][j])py1=j;if(c.y+c.d==xyz[1][j]){py2=j; break;}}for(int j=0;j<lz;j++){if(c.z==xyz[2][j])pz1=j;if(c.z+c.h==xyz[2][j]){pz2=j; break;}}for(int i=px1;i<px2;i++)for(int j=py1;j<py2;j++)for(int k=pz1;k<pz2;k++)pic[i+1][j+1][k+1]=1;} int cnt=0; void fillflood(){ // cout<<"HERE"<<endl;// printf("x %d y %d z %d %d\n",x,y,z,++cnt); qx.push(0); qz.push(0); qy.push(0); while(!qx.empty()){int x=qx.front(),y=qy.front(),z=qz.front();qx.pop(); qy.pop(); qz.pop();//printf("%d %d %d\n",x,y,z);if(x&&y&&z&&x!=lx&&y!=ly&&z!=lz)airv+=lxyz[0][x-1]*lxyz[1][y-1]*lxyz[2][z-1];//printf("x%d %d y%d %d z%d %d\n",x,y,z,lxyz[0][x-1],lxyz[1][y-1],lxyz[2][z-1]);int xi,yi,zi;for(int i=0;i<6;i++){xi=x+dx[i]; yi=y+dy[i]; zi=z+dz[i];if(xi>=0&&xi<lx+1&&yi>=0&&yi<ly+1&&zi>=0&&zi<lz+1){if(!pic[xi][yi][zi]){qx.push(xi); qy.push(yi); qz.push(zi);pic[xi][yi][zi]=2;}else if(pic[xi][yi][zi]==1){// printf("x %d y %d z %d %d\n",x,y,z,++cnt); if(xi!=x)anss+=lxyz[1][y-1]*lxyz[2][z-1];if(yi!=y)anss+=lxyz[0][x-1]*lxyz[2][z-1];if(zi!=z)anss+=lxyz[0][x-1]*lxyz[1][y-1];// printf("%d\n",anss); } } }} }int main(){int m,n;scanf("%d",&m);while(m--){memset(pic,0,sizeof(pic));anss=0; airv=0; scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d%d%d%d%d",&a[i].x,&a[i].y,&a[i].z,&a[i].w,&a[i].d,&a[i].h);xyz[0][2*i]=a[i].x; xyz[0][2*i+1]=a[i].x+a[i].w;xyz[1][2*i]=a[i].y; xyz[1][2*i+1]=a[i].y+a[i].d;xyz[2][2*i]=a[i].z; xyz[2][2*i+1]=a[i].z+a[i].h;}sort(xyz[0],xyz[0]+2*n); //xyz三向离散化 sort(xyz[1],xyz[1]+2*n);sort(xyz[2],xyz[2]+2*n);lx=unique(xyz[0],xyz[0]+2*n)-xyz[0]; //xyz三向离散化 ly=unique(xyz[1],xyz[1]+2*n)-xyz[1];lz=unique(xyz[2],xyz[2]+2*n)-xyz[2];ansv=(xyz[0][lx-1]-xyz[0][0])*(xyz[1][ly-1]-xyz[1][0])*(xyz[2][lz-1]-xyz[2][0]); // cout<<"v "<<ansv<<endl;for(int i=0;i<lx-1;i++){ //计算离散程度 lxyz[0][i]=xyz[0][i+1]-xyz[0][i]; }for(int i=0;i<ly-1;i++){ lxyz[1][i]=xyz[1][i+1]-xyz[1][i]; }for(int i=0;i<lz-1;i++){ lxyz[2][i]=xyz[2][i+1]-xyz[2][i]; }for(int i=0;i<n;i++) fillcube(a[i]);fillflood();ansv-=airv;printf("%d %d\n",anss,ansv);}return 0; }
