例题6-18 雕塑（Sculpture, ACM/ICPC NWERC 2008, UVa12171） 某雕塑由n（n≤50）个边平行于坐标轴的长方体组成。每个长方体用6个整 数x0，y0，z0，x，y，z表示（均为1～500的整数），其中x0为长方体的顶点中x坐标的最小 值，x表示长方体在x方向的总长度。其他4个值类似定义。你的任务是统计这个雕像的体积 和表面积。注意，雕塑内部可能会有密闭的空间，其体积应计算在总体积中，但从“外部”看 不见的面不应计入表面积。雕塑可能会由多个连通块组成。 Sample Input 2 2 1 2 3 3 4 5 6 2 3 3 4 5 7 1 1 1 5 5 1 1 1 10 5 5 1 1 1 2 1 4 8 2 1 2 4 1 8 5 2 2 1 4 8 1 5 2 4 1 8 3 3 4 1 1 1 Sample Output 188 120 250 250
本家地址
关键点：
构造三维数组space来模拟雕像涂色。我们只从空白处开始遍历联通部分，最后使用总体积和面积减去空白部分的。但是不能使用500*500*500的数组，太大。采用离散化。即将雕像分组，因为最多只有50个方块，所以每个方向最多只会有100个分组。使用map来存储坐标值与space中的方位的对应关系。、之后使用常规bfs方式进行方块遍历。不要用dfs，栈溢出。
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std
;
class Cube{
public:
int xyz
[3];
int sss
[3];
};
vector
<Cube
> cubeList
;
map
<int,int> site
[3];
vector
<int> value
[3];
int space
[105][105][105];
queue
<Cube
> temp
;
int getSetIndex(int xyz
, int value
){
return site
[xyz
][value
];
}
long V
;
long S
;
int XX
,YY
,ZZ
;
int check(int x
,int y
,int z
){
if(x
>=0&&x
<XX
&& y
>=0&&y
<YY
&& z
>=0&&z
<ZZ
){
if(space
[x
][y
][z
]==1){
return 1;
}else if(space
[x
][y
][z
]==0){
Cube c
;
c
.xyz
[0]=x
;
c
.xyz
[1]=y
;
c
.xyz
[2]=z
;
temp
.push(c
);
}
return 0;
}else{
return -1;
}
}
int bfs(int x
,int y
,int z
){
Cube c
;
c
.xyz
[0]=x
;
c
.xyz
[1]=y
;
c
.xyz
[2]=z
;
temp
.push(c
);
while(!temp
.empty()){
c
= temp
.front();temp
.pop();
x
= c
.xyz
[0];
y
= c
.xyz
[1];
z
= c
.xyz
[2];
if(x
>=0&&x
<XX
&& y
>=0&&y
<YY
&& z
>=0&&z
<ZZ
){
if(space
[x
][y
][z
]==0){
space
[x
][y
][z
] = 2;
int xs
= value
[0][x
+1] - value
[0][x
];
int ys
= value
[1][y
+1] - value
[1][y
];
int zs
= value
[2][z
+1] - value
[2][z
];
V
+= xs
* ys
* zs
;
int res
;
res
= check(x
-1,y
,z
); S
= S
+ res
* ys
*zs
;
res
= check(x
+1,y
,z
); S
= S
+ res
* ys
*zs
;
res
= check(x
,y
-1,z
); S
= S
+ res
* xs
*zs
;
res
= check(x
,y
+1,z
); S
= S
+ res
* xs
*zs
;
res
= check(x
,y
,z
-1); S
= S
+ res
* xs
*ys
;
res
= check(x
,y
,z
+1); S
= S
+ res
* xs
*ys
;
}
}
}
return 0;
}
int run(int x
,int y
,int z
){
return bfs(x
,y
,z
);
}
void clac(){
for(int i
=0;i
<XX
;i
++){
for(int j
=0;j
<YY
;j
++){
run(i
,j
,0);
run(i
,j
,ZZ
-1);
}
}
for(int i
=0;i
<XX
;i
++){
for(int k
=0;k
<ZZ
;k
++){
run(i
,0,k
);
run(i
,YY
-1,k
);
}
}
for(int j
=0;j
<YY
;j
++){
for(int k
=0;k
<ZZ
;k
++){
run(0,j
,k
);
run(XX
-1,j
,k
);
}
}
int sumX
,sumY
,sumZ
;
if(XX
<0) sumX
= 0; else sumX
= value
[0][XX
]-value
[0][0];
if(YY
<0) sumY
= 0; else sumY
= value
[1][YY
]-value
[1][0];
if(ZZ
<0) sumZ
= 0; else sumZ
= value
[2][ZZ
]-value
[2][0];
int sumS
= (sumX
* sumY
+ sumX
* sumZ
+ sumY
* sumZ
) * 2;
int sumV
= sumX
* sumY
* sumZ
;
cout
<<sumS
+ S
<<" "<<sumV
-V
<<endl
;
}
void init(){
V
=S
=XX
=YY
=ZZ
=0;
cubeList
.clear();
for(int i
=0;i
<3;i
++){
site
[i
].clear();
value
[i
].clear();
}
memset(space
,0,sizeof(space
));
}
int main(){
int T
;
cin
>>T
;
while(T
--){
init();
int N
;
cin
>>N
;
while(N
-- > 0){
Cube b
;
int x
,y
,z
,xs
,ys
,zs
;
cin
>>x
>>y
>>z
>>xs
>>ys
>>zs
;
b
.xyz
[0] = x
;
b
.xyz
[1] = y
;
b
.xyz
[2] = z
;
b
.sss
[0] = xs
;
b
.sss
[1] = ys
;
b
.sss
[2] = zs
;
site
[0][x
] = 0;
site
[1][y
] = 0;
site
[2][z
] = 0;
site
[0][x
+xs
] = 0;
site
[1][y
+ys
] = 0;
site
[2][z
+zs
] = 0;
cubeList
.push_back(b
);
}
for(int i
=0;i
<3;i
++){
map
<int,int>::iterator iter
;
int n
= 0;
for(iter
=site
[i
].begin(); iter
!=site
[i
].end(); iter
++){
value
[i
].push_back(iter
->first
);
iter
->second
= n
;
n
++;
}
}
XX
= value
[0].size()-1;
YY
= value
[1].size()-1;
ZZ
= value
[2].size()-1;
for(int i
=0;i
<cubeList
.size();i
++){
int start
[3];
int end
[3];
for(int ii
=0;ii
<3;ii
++){
start
[ii
] = getSetIndex(ii
, cubeList
[i
].xyz
[ii
]);
end
[ii
] = getSetIndex(ii
, cubeList
[i
].xyz
[ii
] + cubeList
[i
].sss
[ii
]);
}
for(int xi
=start
[0]; xi
<end
[0]; xi
++){
for(int yi
=start
[1]; yi
<end
[1]; yi
++){
for(int zi
=start
[2]; zi
<end
[2]; zi
++){
space
[xi
][yi
][zi
] = 1;
}
}
}
}
clac();
}
return 0;
}
ps：这道题十分美妙。辗转波折，所幸做出，十分感谢。
