例题6-18 雕塑（Sculpture, ACM/ICPC NWERC 2008, UVa12171）

1. dfs递归会栈溢出，只能用bfs来floodfill。试了下Uva 1103不知道该怎么bfs。
2. 三维的floodfill，初步实现竟然过个样例10s，woc。。写的太辣鸡。
3. 看了lrjls的做法，离散化，只求空白的体积，计算涂色边界来求得面积。
4. 感觉还是定义了好多的数组，命名好难受。orz。

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cctype>
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define IN() freopen("in.txt", "r", stdin)
#define OUT() freopen("out.txt", "w", stdout)
#define LL long long
#define maxn 55
#define maxm 1005
#define mod 1000000007
#define INF 1000000007
#define eps 1e-5
#define PI 3.1415926535898
#define N 26
using namespace std;
//-------------------------CHC------------------------------//
int G[maxn << 1][maxn << 1][maxn << 1];
const int dx[] = { 1, 0, 0, -1, 0, 0 };
const int dy[] = { 0, 1, 0, 0, -1, 0 };
const int dz[] = { 0, 0, 1, 0, 0, -1 };
const int total = maxm * maxm * maxm;
int lx[maxn], ly[maxn], lz[maxn], rx[maxn], ry[maxn], rz[maxn];
int nx = 2, ny = 2, nz = 2;
int x[maxn << 1], y[maxn << 1], z[maxn << 1];
struct Node {
	int x, y, z;
	Node(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) { }
	Node next(int i) { return Node(x + dx[i], y + dy[i], z + dz[i]); }
	void vis() { G[x][y][z] = -1; }
	bool is_colored() { return G[x][y][z] == 1; }
	bool is_visited() { return G[x][y][z] == -1; }
	bool check() { return 0 <= x && x < nx - 1 && 0 <= y && y < ny - 1 && 0 <= z && z < nz - 1; }
};

int Vol(Node a) { return (x[a.x + 1] - x[a.x])*(y[a.y + 1] - y[a.y])*(z[a.z + 1] - z[a.z]); }

int Area(Node a, int i) { 
	if (dx[i] != 0) return (y[a.y + 1] - y[a.y])*(z[a.z + 1] - z[a.z]);
	else if (dy[i] != 0) return (x[a.x + 1] - x[a.x])*(z[a.z + 1] - z[a.z]);
	return (x[a.x + 1] - x[a.x])*(y[a.y + 1] - y[a.y]);
}

void discretize(int *arr, int &n) {
	sort(arr, arr + n);
	n = unique(arr, arr + n) - arr;
}

int pos(int *arr, int n, int val) {
	return lower_bound(arr, arr + n, val) - arr;
}

void draw(int lx, int ly, int lz, int rx, int ry, int rz) {
	for (int i = lx; i < rx; ++i)
		for (int j = ly; j < ry; ++j)
			for (int k = lz; k < rz; ++k)
				G[i][j][k] = 1;
}

void bfs(int &vol, int &area) {
	queue<Node> q;
	Node s;
	q.push(s);
	s.vis();
	while (q.size()) {
		Node u = q.front(); q.pop();
		vol += Vol(u);
		for (int i = 0; i < 6; ++i) {
			Node v(u.x + dx[i], u.y + dy[i], u.z + dz[i]);
			if (v.check()) {
				if (v.is_colored()) area += Area(u, i);
				else if(!v.is_visited()){
					v.vis();
					q.push(v);
				}
			}
		}
	}
	vol = total - vol;
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		CLEAR(G, 0);
		int n;
		scanf("%d", &n);
		nx = 2, ny = 2, nz = 2;
		x[0] = y[0] = z[0] = 0;
		x[1] = y[1] = z[1] = maxm;
		for (int i = 0; i < n; ++i) {
			scanf("%d%d%d%d%d%d", &lx[i], &ly[i], &lz[i], &rx[i], &ry[i], &rz[i]);
			rx[i] += lx[i],ry[i] += ly[i], rz[i] += lz[i];
			x[nx++] = lx[i], x[nx++] = rx[i];
			y[ny++] = ly[i], y[ny++] = ry[i];
			z[nz++] = lz[i], z[nz++] = rz[i];
		}
		discretize(x, nx);
		discretize(y, ny);
		discretize(z, nz);
		for (int i = 0; i < n; ++i) {
			int sx = pos(x, nx, lx[i]), tx = pos(x, nx, rx[i]);
			int sy = pos(y, ny, ly[i]), ty = pos(y, ny, ry[i]);
			int sz = pos(z, nz, lz[i]), tz = pos(z, nz, rz[i]);
			draw(sx, sy, sz, tx, ty, tz);
		}
		int vol = 0, area = 0;
		bfs(vol, area);
		printf("%d %d\n", area, vol);
	}
	return 0;
}