首先要注意看懂题目的要求,求体积时，如果有空腔(也就是周围都是实心,中间是空气),也要计入体积,
所以相当于先在外围构造一圈空气,然后用总体积减去外围空气的总体积即可.
第二计算雕塑表面积的时候,实际上就是计算和外围空气有接触的那些面的面积,具体的说，假定从为空气的单元格出发,
走到它的一个邻居时发现邻居为实心,此时应该计算的是源单元格的那个接触面的面积(因为进行离散化处理以后,目标实心格的那一面不一定都和空气接触),这个接触面的面积要根据行走方向来确定.
3，所谓离散化，就是先根据所有实心长方体的两个对角点信息求出所有不同的x,y,z坐标的列表,为了方便计算，每个坐标列表可以再增加一个最小值和和最大值,
然后整个区域把这些不同的区间进行划分,比如离散化之前整个区域有
10*10*10个单元格,然后不同的x坐标有4个,y坐标有5个,z坐标有6个,那么离散化之后要处理的区域数就是(4-1)*(5-1)*(6-1)=60个,
相当于把离散化之前的很多相邻的空心小单元格合并到一起了,加快了处理的效率
4.离散化以后的每个区域只需要知道其左下坐标即可,准确的说是坐标在列表中的编号,离散化的一个好处就是，假定某个区域的左下角的坐标索引为(x,y,z)，那么这个区域的对角点坐标索引一定为(x+1,y+1,z+1),这样就能迅速计算出这个区域的体积和各个面的面积.
下面是ac代码
/*
本代码的思路主要参考了课本原文以及
https://blog.csdn.net/hm970928/article/details/78068515
*/
#include <iostream>
#include <iomanip>
#include <cassert>
#include <list>
#include <cctype>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <iterator>
#include <stack>
#include <string>
#include <vector>
#include <functional>
#include <utility>
#include <sstream>
#ifdef _DEBUG
#include <fstream>
#endif // _DEBUG
using namespace std;
#ifdef _DEBUG
ifstream ifs;
ofstream ofs;
const int UVA_PROBLEM_NO = 12171;
void redirect_input()
{
ostringstream oss;
oss << "uva" << UVA_PROBLEM_NO << "_in.txt";
ifs.open(oss.str().c_str());
cin.rdbuf(ifs.rdbuf());
}
void redirect_output()
{
ostringstream oss;
oss << "uva" << UVA_PROBLEM_NO << "_out.txt";
ofs.open(oss.str().c_str());
cout.rdbuf(ofs.rdbuf());
}
#endif
void main_proc();
int main()
{
#ifdef _DEBUG
redirect_input();
redirect_output();
#endif // _DEBUG
main_proc();
#ifdef _DEBUG
ifs.close();
ofs.close();
#endif
return 0;
}
const bool EMPTY = false;
const bool SOLID = true;
//3维空间中一个节点可能移动的6个方向
const int X_POS = 0;
const int X_NEG = 1;
const int Y_POS = 2;
const int Y_NEG = 3;
const int Z_POS = 4;
const int Z_NEG = 5;
//沿这6个方向移动时,x y z的坐标差
const int dx[] = { 1,-1,0,0,0,0 };
const int dy[] = { 0,0,1,-1,0,0 };
const int dz[] = { 0,0,0,0,1,-1 };
//记录长方体的两个对角点的坐标
struct Box {
int x1;
int y1;
int z1;
int x2;
int y2;
int z2;
void read()
{
cin >> x1 >> y1 >> z1;
int xL, yL, zL;
cin >> xL >> yL >> zL;
x2 = x1 + xL;
y2 = y1 + yL;
z2 = z1 + zL;
}
};
//保存某个网格左下角的坐标索引
struct Cell {
int xindex;
int yindex;
int zindex;
Cell(int xindex = 0, int yindex = 0, int zindex = 0)
:xindex(xindex), yindex(yindex), zindex(zindex)
{
}
void move(int dir) {
xindex += dx[dir];
yindex += dy[dir];
zindex += dz[dir];
}
Cell (const Cell&other)
:xindex(other.xindex)
,yindex(other.yindex)
,zindex(other.zindex)
{
}
Cell& operator=(const Cell&other) {
if (this != &other)
{
xindex = other.xindex;
yindex = other.yindex;
zindex = other.zindex;
}
return *this;
}
void print()const {
cout << "(" << xindex
<< "," << yindex
<< "," << zindex
<< ")"
;
}
};
//把集合里的值依次存到数组里
void convert_to_vector(const set<int>& values, vector<int>&v, map<int, int> & indexes)
{
int min_value = *(values.begin()) - 1;
int max_value = *(values.rbegin()) + 1;
//int min_value = 0;
//int max_value = 1001;
size_t L = values.size()+2;
v.resize(L);
v[0] = min_value;
indexes[min_value] = 0;
v[L - 1] = max_value;
indexes[max_value] = L - 1;
int i = 1;
for (auto & e:values)
{
v[i] = e;
indexes[e] = i;
++i;
}
}
struct Sculpture {
vector<int> x_cors; //x坐标列表
vector<int> y_cors; //y坐标列表
vector<int> z_cors; //z坐标列表
vector<vector<vector<bool> > > grid_color; //网格列表,格子的总数=x坐标的个数*y坐标的个数*z坐标的个数
//对应下标为x y z坐标在各自坐标列表中的下标(都是左下角),值代表颜色
int total_volume; //整个区域的总面积
int area; //雕塑的总表面积
int empty_volume; //外围空气的总体积
int get_volume(const Cell& cell)const {
return get_volume(cell.xindex, cell.yindex, cell.zindex);
}
//计算某个网格的体积
int get_volume(int xindex, int yindex, int zindex)const {
int xL = x_cors[xindex + 1] - x_cors[xindex];
int yL = y_cors[yindex + 1] - y_cors[yindex];
int zL = z_cors[zindex + 1] - z_cors[zindex];
#if 0
if (xindex == 1 && yindex == 1 && zindex == 0)
{
cout << endl;
cout << "xL=" << x_cors[xindex + 1] <<"-"<< x_cors[xindex]
<<"="<< xL << endl;
cout << "yL=" << y_cors[yindex + 1] << "-" << y_cors[yindex]
<< "=" << yL << endl;
cout << "zL=" << z_cors[zindex + 1] << "-" << z_cors[zindex]
<< "=" << zL << endl;
}
#endif
return xL * yL * zL;
}
int get_area(const Cell& cell, int dir) {
return get_area(cell.xindex, cell.yindex, cell.zindex, dir);
}
/*沿方向dir遇到左下坐标为(x,y,z)的网格时,计算接触面的面积
比如如果是沿x轴方向接触到这个格子时,那么表面积就是yL*zL,另外两个方向类似
*/
int get_area(int xindex, int yindex, int zindex, int dir)const
{
int area = 0;
int xL = x_cors[xindex + 1] - x_cors[xindex];
int yL = y_cors[yindex + 1] - y_cors[yindex];
int zL = z_cors[zindex + 1] - z_cors[zindex];
switch (dir)
{
case X_POS:
case X_NEG:
area = yL * zL;
break;
case Y_POS:
case Y_NEG:
area = xL * zL;
break;
case Z_POS:
case Z_NEG:
area = xL * yL;
break;
default:
break;
}
return area;
}
void init(const vector<Box>& boxes) {
set<int> sx;
set<int> sy;
set<int> sz;
for (auto &e: boxes){
sx.insert(e.x1);
sx.insert(e.x2);
sy.insert(e.y1);
sy.insert(e.y2);
sz.insert(e.z1);
sz.insert(e.z2);
}
map<int, int> x_indexes; //每个x坐标在列表中的下标
map<int, int> y_indexes; //每个y坐标在列表中的下标
map<int, int> z_indexes; //每个z坐标在列表中的下标
convert_to_vector(sx, x_cors, x_indexes);
convert_to_vector(sy, y_cors, y_indexes);
convert_to_vector(sz, z_cors, z_indexes);
size_t nx = x_cors.size();
size_t ny = y_cors.size();
size_t nz = z_cors.size();
//首先把所有网格都设为空气
grid_color = vector<vector<vector<bool> > >(nx,
vector<vector<bool> >(ny, vector<bool>(nz, EMPTY)));
//把每个长方体内部含有的所有网格的颜色都设为实心
for (auto &e : boxes) {
int start_xindex = x_indexes[e.x1];
int end_xindex = x_indexes[e.x2];
int start_yindex = y_indexes[e.y1];
int end_yindex = y_indexes[e.y2];
int start_zindex = z_indexes[e.z1];
int end_zindex = z_indexes[e.z2];
for (int i=start_xindex;i<end_xindex;++i)
for (int j = start_yindex;j<end_yindex;++j)
for (int k = start_zindex;k<end_zindex;++k)
{
grid_color[i][j][k] = SOLID;
}
}
}
//计算整个区域的面积
int get_total_volume()const{
int xL = x_cors.back() - x_cors[0];
int yL = y_cors.back() - y_cors[0];
int zL = z_cors.back() - z_cors[0];
return xL * yL * zL;
}
bool in_side(const Cell& cell)const {
return in_side(cell.xindex, cell.yindex, cell.zindex);
}
bool in_side(int xindex, int yindex, int zindex)const
{
size_t nx = x_cors.size();
size_t ny = y_cors.size();
size_t nz = z_cors.size();
return (xindex >= 0 && xindex + 1 < nx)
&& (yindex >= 0 && yindex + 1 < ny)
&& (zindex >= 0 && zindex + 1 < nz);
}
//计算空气的总体积和雕塑的总表面积
void floodfill(int &volume,int &area)
{
int empty_volume = 0;
queue<Cell> q;
Cell start(0, 0, 0);
size_t nx = x_cors.size();
size_t ny = y_cors.size();
size_t nz = z_cors.size();
//记录某个网格(它一定是空气)是否被访问过,用于防止bfs中重复访问
vector<vector<vector<bool> > >
visited_flag(nx,vector<vector<bool> >(ny,vector<bool>(nz,false)));
q.push(start);
visited_flag[0][0][0] = true;
while (!q.empty())
{
Cell cell = q.front();
//cout << "cell=";
//cell.print();
q.pop();
int t1 = get_volume(cell);
//cout << ",volume=" << t1;
empty_volume += t1; //在这里累加空气体积,而不是在下面的for循环内部累加每个邻居
//那样的话会把第一个节点的体积漏算!
//对cell的每个邻居进行处理
for (int dir=0;dir<6;++dir)
{
Cell neighbour = cell;
neighbour.move(dir);
if (in_side(neighbour))
{
//是空气,且没访问过
if (grid_color[neighbour.xindex][neighbour.yindex][neighbour.zindex]
==EMPTY
&& !visited_flag[neighbour.xindex][neighbour.yindex][neighbour.zindex]
)
{
visited_flag[neighbour.xindex][neighbour.yindex][neighbour.zindex] = true;
q.push(neighbour); //把这个邻居放入队列
}
else if (grid_color[neighbour.xindex][neighbour.yindex][neighbour.zindex]
== SOLID)
{
//邻居是雕塑的一部分,则把与空气接触的表面积累加进去
int t2= get_area(cell, dir);
/*
上面的式子不能写成
int t2= get_area(neighbour, dir);
因为邻居的表面不一定于空气全接触!!!!!
*/
area += t2;
//cout << ",dir=" << dir << ",area=" << t2;
}
}
}
//cout << endl;
}
int v = get_total_volume();
volume = v - empty_volume;
}
};
void main_proc()
{
int casenum = 0;
cin >> casenum;
while(casenum--)
{
int N;
cin >> N;
vector<Box> boxes(N);
for (int i=0;i<N;++i)
boxes[i].read();
Sculpture s;
s.init(boxes);
int volume = 0;
int area = 0;
s.floodfill(volume, area);
cout << area << " "<< volume << endl;
}
}
文章评论