例题 6-18 雕塑（Sculpture，ACM/ICPC NWERC 2008，UVa12171)

原题链接：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;
}