紫书刷题 UVA12171 雕塑(Sculpture)

前排提醒： 一个萌新，有较多不足.

UVA12171

Imagine a box, made of copper plate. Imagine a second one, intersecting the rst one, and several others, intersecting each other (or not). That is how the sculptor Oto Boxing constructs his sculptures. In fact he does not construct that much, he only makes the design; the actual construction is contracted out to a construction company. For the calculation of the costs of construction the company needs to know the total area of copper plate involved. Parts of a box that are hidden in another box are not realized in copper, of course. (Copper is quite expensive, and prices are rising.) After construction, the total construction is plunged into a bath of chemicals. To prevent this bath from running over, the construction company wants to know the total volume of the construction. Given that a construction is a collection of boxes, you are asked to calculate the area and the volume of the construction.

Some of Oto’s designs are connected, others are not. Either way, we want to know the total area and the total volume. It might happen that the boxes completely enclose space that is not included in any of the boxes (see the second example below). Because the liquid cannot enter that space, its volume must be added to the total volume. Copper plate bordering this space is superfluous, of course, so it does not add to the area.

输入格式：

On the rst line one positive number: the number of testcases, at most 100. After that per testcase:
• One line with an integer n (1 ≤ n ≤ 50): the number of boxes involved.
• n lines with six positive integers x0, y0, z0,x , y, z (1 ≤ x0, y0, z0, x, y, z ≤ 500): the triple (x0, y0, z0) is the vertex of the box with the minimum values for the coordinates and the numbers x, y, z are the dimensions of the box (x, y and z dimension, respectively). All dimensions are in centimeters. The sides of the boxes are always parallel to the coordinate axes.

输出格式：

Per testcase:
• One line with two numbers separated by single spaces: the total amount of copper plate needed (in cm2), and the total volume (in cm3).

输入样例：

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

输出样例：

188 120
250 250

题目大意：

摘自紫书

某雕塑由n(n≤50)个边平行坐标轴的长方体组成。每个长方体用6个整数x₀, y₀,z₀, x, y,z表示(均为1-500的整数)，其中x₀为长方体的顶点中x坐标的最小值，x表示长方体在x方向的总长度。其他4个值类似定义。你的任务是统计这个雕像的体积和表面积。注意，雕塑内部可能会有密闭的空间，其体积应计算在总体积中，但从“外部”看不见的面不应计入表面积。雕塑可能会由多个连通块组成.设想有一个三维坐标范围均为1-500 个三维网格，如果一开始就把输入的n个长方体画"到网格里，接下来就可以抛开那些长方体，只在网格中进行统计了。

还记得floodfill吗?它不仅能求出连通块的个数，还能准确地找出每个连通块各由哪些方格组成。虽然本题的研究对象是三维空间中的长方体，但经毫不都响floodfill的作用，唯一的区别就是每个格子的相部格子从二维情形的4个增加到了三维情形的6个。

本题的麻烦之处在于雕塑中间可能有封闭区域，甚至还有可能相互嵌套，看上去很复杂。但其实可以从反面思考:不考虑着塑本身，而考虑“空气”。在网格周围加圈“空气”(目的是为了让所有空气格子连通)，然后做一次floodfill就可以得到空气的“内表面积”和体积。这个表面积就是雕塑的外表面积，而雕塑体积等于总体积减去空气体积。

但还有一个大问题:空间占用。坐标为1-500的整数，一共需要500³=1.25*10⁸个单元。在第5章的例题“城市正视图”中介绍了离散化法，在这里它再次派上用场:每个维度最多只有2n≤100个不同的坐标，因此可以把500*500*500的网格离散化成100*100*100，单元格的数目降为原来的1/125。在foofll时直接使用高散化后的新网格，但在统计表面积和体积时则需要使用原始坐标。

思路：

开学了，而且最近在写前端，刷题时间少了，刷的题水题较多，就没怎么写博客。但这个题卡了我半周了，总是不能很好地理解算法，我觉得把这道题自己的思路记录下来还是很有必要的。学校有个编程马拉松的活动，过段时间应该会变得高产，日更两题了。

这道题跟之前的UVA221城市正视图(Urban Elevations)都采用了离散化的算法降低了时空复杂度。如果要初步了解离散化算法的概念和优势，可以看一看知乎上兔子牙不齐的这篇文章：离散化的概念及优势。

为了解决金属格子嵌套的情况，采用了四周补空气，floodfill空气块来间接计算金属块体积与表面积的算法。这与之前的UVA1103古代象形符号(Acient Messages)有异曲同工之妙。

用六个整型一维数组储存原始数据。用三个整型一维数组储存离散化数据。用一个三维整型数组color表示离散化后的三维立体网格，用以储存哪里是空气块哪里是金属块。

查找算法使用的是lower_bound()，底层是二分查找，时间复杂度接近常数级。

Cell类创建的对象表示离散化后的三维立体网格中的一个单位格子。

y0和y1在math.h中被定义过了，有可能需要换一个名字。

处理过程：

1.读入数据，并将格子真实的左右边界储存在原始数据数组中。
2.将左右边界压入待离散化数组中。
3.将三个待离散化数组进行离散化。
4.画格子（把金属格子标记出来）
5.从(0, 0, 0)这个空气块开始用bfs（防止爆栈，不用dfs）开始floodfill。计算出空气连通块的表面积和体积，间接计算出金属块的表面积和体积。
6.输出。

刘汝佳代码：

// UVa12171 Sculpture
// Rujia Liu
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int maxn = 50 + 5;
const int maxc = 1000 + 1;

// original data
int n, x0[maxn], y0[maxn], z0[maxn], x1[maxn], y1[maxn], z1[maxn];

// discretization related
int nx, ny, nz;
int xs[maxn * 2], ys[maxn * 2], zs[maxn * 2];

// floodfill related
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 };
int color[maxn * 2][maxn * 2][maxn * 2];

struct Cell {
    int x, y, z;
    Cell(int x = 0, int y = 0, int z = 0) :x(x), y(y), z(z) {}
    bool valid() const {
        return x >= 0 && x < nx - 1 && y >= 0 && y < ny - 1 && z >= 0 && z < nz - 1;
    }
    bool solid() const {
        return color[x][y][z] == 1; // solid
    }
    bool getVis() const {
        return color[x][y][z] == 2; // visited
    }
    void setVis() const {
        color[x][y][z] = 2;
    }
    Cell neighbor(int dir) const {
        return Cell(x + dx[dir], y + dy[dir], z + dz[dir]);
    }
    int volume() const {
        return (xs[x + 1] - xs[x]) * (ys[y + 1] - ys[y]) * (zs[z + 1] - zs[z]);
    }
    int area(int dir) const {
        if (dx[dir] != 0) return (ys[y + 1] - ys[y]) * (zs[z + 1] - zs[z]);
        else if (dy[dir] != 0) 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;
}

int ID(int* x, int n, int x0) {
    return lower_bound(x, x + n, x0) - x;
}

void floodfill(int& v, int& s) {
    v = 0;
    s = 0;
    Cell c;
    c.setVis();
    queue<Cell> q;
    q.push(c);
    while (!q.empty()) {
        Cell c = q.front(); q.pop();
        v += c.volume();
        for (int i = 0; i < 6; i++) {
            Cell c2 = c.neighbor(i);
            if (!c2.valid()) continue;
            if (c2.solid()) s += c.area(i);
            else if (!c2.getVis()) {
                c2.setVis();
                q.push(c2);
            }
        }
    }
    v = maxc * maxc * maxc - v;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        nx = ny = nz = 2;
        xs[0] = ys[0] = zs[0] = 0;
        xs[1] = ys[1] = zs[1] = maxc;
        scanf("%d", &n);
        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);

        // paint
        memset(color, 0, sizeof(color));
        for (int i = 0; i < n; i++) {
            int X1 = ID(xs, nx, x0[i]), X2 = ID(xs, nx, x1[i]);
            int Y1 = ID(ys, ny, y0[i]), Y2 = ID(ys, ny, y1[i]);
            int Z1 = ID(zs, nz, z0[i]), Z2 = ID(zs, nz, z1[i]);
            for (int X = X1; X < X2; X++)
                for (int Y = Y1; Y < Y2; Y++)
                    for (int Z = Z1; Z < Z2; Z++)
                        color[X][Y][Z] = 1;
        }

        int v, s;
        floodfill(v, s);
        printf("%d %d\n", s, v);
    }

    return 0;
}