例题6-18 UVA12171 Sculpture（90行AC代码）

紫书刷题进行中，题解系列【GitHub|CSDN】

例题6-18 UVA12171 Sculpture（90行AC代码）

题目大意

给定笛卡尔坐标系上的长方体左下角坐标和对应边长，长方体间存在相离，相切，相交等各种关系，求总体的体积和表面积，对于完全被长方体包围的空间计算器体积而忽略面积。

思路分析

极好的一道题目，综合性强，思维量大，技巧性强，编码量大

强烈建议完全弄懂分析思路，写代码是水到渠成的事

问题1：完全没有思路怎么办？
答案1：构造三维网格，离散化/微元切割，空间换时间

一眼看去，毫无头绪，难点关键在于长方体间复杂关系的处理，那么可假想有一个足够大的三维网格，每个格子体积为单位1，输入长方体时填充相应网格，最后直接统计网格即可，这样顺利的避免了长方体复杂的关系处理。这个思路运用了两个设计思想：

• 离散化/微元切割：将复杂的物体用规则的网格替代计算，将所有运算转换为加法（类似于微积分思想，取微元，近似为规则的长方形或三角形处理）

• 空间换时间：三维网格足够大，每个格子有二元状态，即属于长方体或不属于长方体，每个格子内部状态等效，有效简化了逻辑的复杂度

问题2：网格使用的空间超过限制怎么办？
答案2：离散化技巧

看起来很美好，但是本题坐标最大值为1000，意味着最大空间需10^{9，显然需要进行空间优化，可以考虑**离散化**技巧（[类似UVA221](https://blog.csdn.net/qq_40738840/article/details/104217617)，它是二维离散化），这里是三维，本质是一样的，将连续无限的状态转换为离散有限状态。本题最多有50个点，因此最多有100个位置，这里空间仅需10}6，完全满足。

问题3：怎么计算铜块体积和面积？
答案3：整体局部做差法，逆向思维，连通块floodfill

由于铜块内部关系错综复杂，我们可以转为计算空气的体积（这里需要一点想象力），再用网格总体积减去空气体积，即可得到铜块体积；而面积就是空气的内表面积。关于体积面积可用连通块算法计算（英文名floodfill：意为像洪水填充物体，有孔则入；实现用bfs/dfs）

问题4：计算空气体积和面积时，空气可能存在多个连通块？
答案4：补边法（在三维网格外围增加一层空气网格）

类似于UVA1103，在外围补一层空白网格，将所有空气连通块打通，成为一块（类似打通任督二脉，九九归一）

顺便总结下**离散技巧（类似等效法，划分出一个内部状态均等效的单元，从而用一个点代替一部分）**使用时问题的特征，对应解决策略和实现技巧（只看是理解不了的，建议做题）

问题特征	解决策略	编码实现
复杂关系	微元降解，每个单元内部任意一点状态等价	存储原有数据，计算目标结果
无限状态	离散化，单元的数量降为有限可数	一般是排序，存储离散化数据，用于算法计算

算法设计

本题算法设计也极具借鉴意义，先看数据结构（必须理解思路分析中的离散法技巧）

const int maxn=55, maxp=1001; // 长方体个数最大值，坐标最大值
int color[maxn*2][maxn*2][maxn*2]; // 标记长方体是空气还是铜盘，bfs使用；0空气，1铜盘，2空气已访问
int x0[maxn], x1[maxn], y0[maxn], y1[maxn], z0[maxn], z1[maxn]; // 原始数据，每个长方体的xyz边长起止位置
int xs[2*maxn], ys[2*maxn], zs[2*maxn]; // 离散化坐标：xs存储x0和x1中所有去重升序排列后的坐标
int nx, ny, nz; // 记录xs,ys,zs的长度
int dirt[6][3]={{+1,0,0},{-1,0,0}, {0,+1,0},{0,-1,0}, {0,0,+1},{0,0,-1}}; // 沿着x,y,z轴的6个方向的方向向量

其中最为重要的莫过于存储离散化坐标的xs,ys,zs和标记离散化后的网格的状态的三维数组color（注意此时用长方体的左下角坐标代表整个长方体，即利用离散化的等效原则：长方体内任意一点状态一致）。有了这些就足够完成floodfill了，那么为何要记录原始数据？因为题目要求计算出最终的体积和面积，因此需要带入真正的数据。那么怎么保证访问原始数据的速度？因为离散化后的坐标均为升序序列，可用二分查找，时间接近常数。

int getId(int *a, int n, int val) { // 获取val在数组a中的下标
    return lower_bound(a, a+n, val) - a; // 复杂度logn，接近常数查找
}

同时为了便于floodfill算法的实现，封装Cell结构体，内含x,y,z成员表示离散化后的网格坐标，他们实际上是索引，例如xs[x+1]-xs[x]表示左下角为(x,y,z)的离散化后的长方体的x方向边长；同时也封装了常用的构造函数，面积和体积计算函数。对于面积计算有些技巧

在floodfill时遇到铜块则需要计算面积，那么由两个问题需回答：

问题5：空气块A紧邻有铜块B，该用谁来计算面积？
回答5：空气块A

若用铜块B计算，可能导致重复计算。因为一个铜块可能与多个空气块接触，floodfill过程中会遍历每一个空气块，若每次均用铜块B计算，那么会导致B的部分面积重复计算，因此选用空气块A

问题6：该计算空气块A的哪一个面？
答案6：与铜块相邻的面（与移动方向垂直的面）

上面定义了方块移动的6个方向，若A和B沿x轴相邻，则计算y*z的面积，依次类推

问题7：floodfill用dfs还是bfs实现？
答案7：bfs（dfs在状态多时容易爆栈）

剩余的就是老老实实，仔仔细细的写代码和调试了

注意点

• 因为给三维网格增加一层外围空气块，需注意在离散化时处理该问题

• 变量x0,y0,y1.....与头文件math.h中的变量定义冲突，建议不用万能头文件或者更换变量名

• 注意计算内表面积时算的是空气块部分的接触面积，否则会重复计算

• 用unique和lower_bound函数前必须保证序列有序，二者均返回迭代器/指针

• 结构体和类很像，可以利用它封装函数，简化代码，提高可读性

• 建议理解透彻在动手写代码

AC代码（C++11，离散化，floodfill/bfs）

// #include<bits/stdc++.h> // 不要用万能头文件,math.h中的x0,x1...会产生冲突
#include <cstdio> // scanf,printf
#include <algorithm> // sort,lower_bound
#include <queue> // queue
#include <cstring> // memset()
using namespace std; // 默认命名空间

const int maxn=55, maxp=1001; // 长方体个数最大值，坐标最大值
int color[maxn*2][maxn*2][maxn*2]; // 标记长方体是空气还是铜盘，bfs使用；0空气，1铜盘，2空气已访问
int x0[maxn], x1[maxn], y0[maxn], y1[maxn], z0[maxn], z1[maxn]; // 原始数据，每个长方体的xyz边长起止位置
int xs[2*maxn], ys[2*maxn], zs[2*maxn]; // 离散化坐标：xs存储x0和x1中所有去重升序排列后的坐标
int nx, ny, nz; // 记录xs,ys,zs的长度
int dirt[6][3]={{+1,0,0},{-1,0,0}, {0,+1,0},{0,-1,0}, {0,0,+1},{0,0,-1}}; // 沿着x,y,z轴的6个方向
int getId(int *a, int n, int val) { // 获取val在数组a中的下标
    return lower_bound(a, a+n, val) - a; // 复杂度logn，接近常数查找
}
struct Cell { // 存储逻辑上的长方体
    int x, y, z; // 用来bfs的坐标，表示长方体左下角
    Cell (int _x, int _y, int _z) : x(_x), y(_y), z(_z) {} // 构造函数
    bool isValid() {return (0 <= x && x < nx-1) && (0 <= y && y < ny-1) && (0 <= z && z < nz-1);} // 判断位置是否合法
    Cell getNeighbor(int dir) {return Cell(x+dirt[dir][0], y+dirt[dir][1], z+dirt[dir][2]);} // 返回dir方向的邻居
    int getVolume() { // 计算体积
        return (xs[x+1]-xs[x]) * (ys[y+1]-ys[y]) * (zs[z+1]-zs[z]); // 长*宽*高
    }
    int getArea(int dir) { // 根据方向获取内表面积
        if (dirt[dir][0] != 0) return (ys[y+1] - ys[y]) * (zs[z+1] - zs[z]); // 空气从x轴接触铜块，面积为y*z
        else if (dirt[dir][1] != 0) return (xs[x+1] - xs[x]) * (zs[z+1] - zs[z]); // 空气从y轴接触铜块
        else if (dirt[dir][2] != 0) return (xs[x+1] - xs[x]) * (ys[y+1] - ys[y]); // 空气从z轴接触铜块
        return -1; // 表示出错
    }
    bool isCopper() {return color[x][y][z] == 1;} // 判断是否为铜块
    bool isVisited() {return color[x][y][z] == 2;} // 若为空气，判断是否被访问
    void setVisited() {color[x][y][z] = 2;} // 设置为已访问
};
void discretize(int *a, int& n) { // 升序排列a，并去重；n为a的逻辑长度，注意引用
    sort(a, a+n); // 先排序
    n = unique(a, a+n) - a; // unique返回去重后的逻辑列表末尾指针
}
void bfs(int& v, int& m) { // 计算体积和表面积
    queue<Cell> q;
    q.push(Cell(0,0,0)); color[0][0][0] = 2; // 初始化，从加入的外围白边开始
    while (!q.empty()) {
        Cell cell = q.front(); q.pop();
        v += cell.getVolume(); // 累加空气体积
        for (int i=0; i < 6; i ++) { // 6个方向
            Cell neb = cell.getNeighbor(i); // 获取邻居
            if (neb.isValid()) { // 邻居有效
                // if (neb.isCopper()) m += neb.getArea(i); // 是铜块则累加从i方向接触的表面积
                if (neb.isCopper()) m += cell.getArea(i); // 是铜块则累加从i方向接触的表面积，若用neb计算面积，会导致重复计算
                else if (!neb.isVisited()) { // 未访问的空气块
                    neb.setVisited(); // 设为已访问
                    q.push(neb); // 加入队列
                }
            }
        }
    }
    v = (maxp*maxp*maxp) - v; // 铜块体积=总体积-空气体积
}
int main() {
    int T, n, lx, ly, lz; scanf("%d", &T);
    while (T --) {
        scanf("%d", &n);
        xs[0] = 0, ys[0] = 0, zs[0] = 0; // 增加一层外围起点
        xs[1] = maxp, ys[1] = maxp, zs[1] = maxp; // 外围终点
        nx = ny = nz = 2; // 当前长度
        for (int i=0; i < n; i ++) {
            scanf("%d %d %d %d %d %d", &x0[i], &y0[i], &z0[i], &lx, &ly, &lz);
            x1[i] = x0[i] + lx; y1[i] = y0[i] + ly; z1[i] = z0[i] + lz; // 终止位置
            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); // 离散化三维坐标
        memset(color, 0, sizeof(color)); // 初始化
        for (int i=0; i < n; i ++) { // 遍历n个长方体，标记铜块
            int X0 = getId(xs, nx, x0[i]), X1 = getId(xs, nx, x1[i]); // 获取x0[i]在xs中的位置
            int Y0 = getId(ys, ny, y0[i]), Y1 = getId(ys, ny, y1[i]);
            int Z0 = getId(zs, nz, z0[i]), Z1 = getId(zs, nz, z1[i]);
            for (int x=X0; x < X1; x ++) { // (x,y,z)为铜块的左下角坐标
                for (int y=Y0; y < Y1; y ++) 
                    for (int z=Z0; z < Z1; z ++) {
                        color[x][y][z] = 1; // 标记左下角为(x,y,z)的长方体为铜块
                    }
            }
        }
        int v=0, m=0; // 体积，面积
        bfs(v, m); // floodfill类似连通块求解,dfs可能会超时
        printf("%d %d\n", m, v); // 面积，体积
    }
    return 0;
}