原题链接：https://vjudge.net/problem/UVA-12171 分类：图 备注：理解离散化；floodfill
紫书思路：利用离散化把三维图缩小，用floodfill求出外围空气体积和内表面积，总体积减去空气体积即所求体积，内表面积即所求表面积。
离散化知识参考：https://blog.csdn.net/tlonline/article/details/46964693 对应练习题：https://vijos.org/p/1056
参考题解博文：https://blog.csdn.net/qq_40738840/article/details/104403108 感谢该文章让我懂了离散化是怎么样实际来使用的，好歹可以AC上面那个练习题了。下述代码也是借鉴了大半。
代码如下：
#include<cstdio> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int dir[6][3] = { {1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1}, {0,0,-1} }; const int maxn = 50 + 5; const int maxp = 1001; int t, n; int sx[maxn], sy[maxn], sz[maxn], ex[maxn], ey[maxn], ez[maxn]; int dx[maxn * 2], dy[maxn * 2], dz[maxn * 2], g[maxn * 2][maxn * 2][maxn * 2]; void discretize(int *a, int& len) { sort(a, a + len); len = unique(a, a + len) - a; } int getId(int* a, int len, int val) { return lower_bound(a, a + len, val) - a; } struct node { int x, y, z; node(int _x, int _y, int _z) :x(_x), y(_y), z(_z) {} }; int main(void) { scanf("%d", &t); while (t--) { memset(g, 0, sizeof(g)); scanf("%d", &n); dx[0] = dy[0] = dz[0] = 0; dx[1] = dy[1] = dz[1] = maxp; //相当于率先规定了一个大的空气块,左下角坐标为(0,0,0),沿对应轴长度为1001,1001,1001,总体积就为1001^3 int lenx = 2, leny = 2, lenz = 2; for (int i = 0; i < n; i++) { int lx, ly, lz; scanf("%d %d %d %d %d %d", &sx[i], &sy[i], &sz[i], &lx, &ly, &lz); ex[i] = sx[i] + lx; ey[i] = sy[i] + ly; ez[i] = sz[i] + lz; dx[lenx++] = sx[i]; dx[lenx++] = ex[i]; dy[leny++] = sy[i]; dy[leny++] = ey[i]; dz[lenz++] = sz[i]; dz[lenz++] = ez[i]; } discretize(dx, lenx); discretize(dy, leny); discretize(dz, lenz); for (int i = 0; i < n; i++) { int st_x = getId(dx, lenx, sx[i]); int ed_x = getId(dx, lenx, ex[i]); int st_y = getId(dy, leny, sy[i]); int ed_y = getId(dy, leny, ey[i]); int st_z = getId(dz, lenz, sz[i]); int ed_z = getId(dz, lenz, ez[i]); //g[x][y][z]代表x-x+1,y-y+1,z-z+1一整个方块 for (int i = st_x; i < ed_x; i++) for (int j = st_y; j < ed_y; j++) for (int k = st_z; k < ed_z; k++) g[i][j][k] = 1; } int Volum = 0, Area = 0; queue<node>Q; Q.push(node(0, 0, 0)); g[0][0][0] = 2; while (!Q.empty()) { node u = Q.front(); Q.pop(); Volum += (dx[u.x + 1] - dx[u.x]) * (dy[u.y + 1] - dy[u.y]) * (dz[u.z + 1] - dz[u.z]); for (int i = 0; i < 6; i++) { int tx = u.x + dir[i][0]; int ty = u.y + dir[i][1]; int tz = u.z + dir[i][2]; if (tx < 0 || ty < 0 || tz < 0 || tx >= lenx - 1 || ty >= leny - 1 || tz >= lenz - 1)continue; if (g[tx][ty][tz] == 1) { if (dir[i][0] != 0) Area += (dy[u.y + 1] - dy[u.y]) * (dz[u.z + 1] - dz[u.z]); else if (dir[i][1] != 0) Area += (dx[u.x + 1] - dx[u.x]) * (dz[u.z + 1] - dz[u.z]); else if (dir[i][2] != 0) Area += (dx[u.x + 1] - dx[u.x]) * (dy[u.y + 1] - dy[u.y]); } else if (g[tx][ty][tz] == 0) { g[tx][ty][tz] = 2; Q.push(node(tx, ty, tz)); } } } Volum = maxp * maxp * maxp - Volum; printf("%d %d\n", Area, Volum); } return 0; }