1.题目描述：点击打开链接
2.解题思路：这道题是紫书上的例题，不过只有解题思路，意思是先将外围包裹一圈空气，然后从空气入手进行floodfill，这之前还要进行“离散化”处理，最后计算体积时用总体积减去外围空气的体积；经过了三天的思考与编程，终于编出来了，不过总是RE，没办法只好换了一种思路：也是从外围空气入手，但直接统计体积和表面积。最后终于AC了，不容易啊。。。
3.代码：
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<map>
#include<sstream>
#include<queue>
#include<cctype>
using namespace std;
typedef long long ll;
const int maxn = 100 + 30;
const int maxm = 50 + 5;
int g[maxn][maxn][maxn];
int x[maxn], y[maxn], z[maxn];
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 };
map<int, int>X, Y, Z;
int n;
ll space, vol, air;
int xnum, ynum, znum;
int mx, my, mz;
struct rec
{
int id;
int x0, y0, z0, x, y, z;
bool operator <(const rec&b)
{
return x0 < b.x0 || (x0 == b.x0&&y0 < b.y0) || (x0 == b.x0&&y0 == b.y0&&z0 < b.z0);
}
}r[maxm];
struct coord
{
int x, y, z;
coord(int i, int j, int k) :x(i), y(j), z(k){}
};
void draw(int pos, int id)
{
int x1 = X[r[pos].x0], x2 = X[r[pos].x + r[pos].x0];
int y1 = Y[r[pos].y0], y2 = Y[r[pos].y + r[pos].y0];
int z1 = Z[r[pos].z0], z2 = Z[r[pos].z + r[pos].z0];
for (int i = x1; i < x2; i++)
for (int j = y1; j < y2; j++)
for (int k = z1; k < z2; k++)
g[i][j][k] = id;
}
int main()
{
int t;
cin >> t;
while (t--)
{
air = 0;
cin >> n;
memset(g, 0, sizeof(g));
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
memset(z, 0, sizeof(z));
for (int i = 0; i < n; i++)
{
scanf("%d%d%d%d%d%d", &r[i].x0, &r[i].y0, &r[i].z0, &r[i].x, &r[i].y, &r[i].z);
r[i].id = i + 1;
x[i * 2 + 1] = r[i].x0, x[i * 2 + 2] = r[i].x + r[i].x0;
y[i * 2 + 1] = r[i].y0, y[i * 2 + 2] = r[i].y + r[i].y0;
z[i * 2 + 1] = r[i].z0, z[i * 2 + 2] = r[i].z + r[i].z0;
}
sort(r, r + n);
sort(x + 1, x + n * 2 + 1);
sort(y + 1, y + n * 2 + 1);
sort(z + 1, z + n * 2 + 1);
xnum = unique(x + 1, x + n * 2 + 1) - (x + 1);
ynum = unique(y + 1, y + n * 2 + 1) - (y + 1);
znum = unique(z + 1, z + n * 2 + 1) - (z + 1);
x[0] = y[0] = z[0] = -1;
vol = 0;
space = 0;
for (int i = 1; i <= xnum; i++)
X[x[i]] = i;
for (int i = 1; i <= ynum; i++)
Y[y[i]] = i;
for (int i = 1; i <= znum; i++)
Z[z[i]] = i;
for (int i = 0; i < n; i++)
draw(i, r[i].id);
vector<coord>q;
q.push_back(coord(0, 0, 0));
while (!q.empty())
{
coord cd = q.back(); q.pop_back();
int i = cd.x, j = cd.y, k = cd.z;
for (int d = 0; d < 6; d++)
{
int nx = i + dx[d];
int ny = j + dy[d];
int nz = k + dz[d];
if (nx >= 0 && ny >= 0 && nz >= 0 && nx <= xnum && ny <= ynum & nz <= znum && !g[nx][ny][nz])
{
g[nx][ny][nz] = -1;
q.push_back(coord(nx, ny, nz));
}
}
}
for (int i = 1; i < xnum;i++)
for (int j = 1; j < ynum;j++)
for (int k = 1; k < znum; k++)
{
int l1 = x[i + 1] - x[i], l2 = y[j + 1] - y[j], l3 = z[k + 1] - z[k];
if (g[i][j][k] != -1)vol += l1*l2*l3;
for (int d = 0; d < 6;d++)
if (g[i][j][k] != -1 && g[i + dx[d]][j + dy[d]][k + dz[d]] == -1)
space += dx[d] ? l2*l3 : dy[d] ? l1*l3 : l1*l2;
}
cout << space << ' ' << vol << endl;
}
return 0;
}
最后附上一份参考代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
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 };
int compress(int n, int *x, int *v) {//进行状态压缩，之后每个边的实际长度存放在v数组，
memcpy(v, x, sizeof(int)*n);
v[n] = -1;//设置该点的作用是让最小的下标从1开始，，从1开始还有一个作用是将来能够给外围加一圈空气；
sort(v, v + n + 1);
int m = unique(v, v + n + 1) - v;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) if (x[i] == v[j]) { x[i] = j; break; }
return m;//返回的是左闭右开区间的长度
}
int occ[110][110][110];
void solve() {
int N;
scanf("%d", &N);
int X[150], Y[150], Z[150];
int xv[150], yv[150], zv[150];
for (int i = 0; i < N; ++i) {
scanf("%d%d%d%d%d%d", X + 2 * i, Y + 2 * i, Z + 2 * i, X + 2 * i + 1, Y + 2 * i + 1, Z + 2 * i + 1);
X[2 * i + 1] += X[2 * i]; Y[2 * i + 1] += Y[2 * i]; Z[2 * i + 1] += Z[2 * i];
}
int xn = compress(2 * N, X, xv);
int yn = compress(2 * N, Y, yv);
int zn = compress(2 * N, Z, zv);
memset(occ, 0, sizeof(occ));
for (int i = 0; i < N; ++i)
for (int x = X[2 * i]; x < X[2 * i + 1]; ++x)
for (int y = Y[2 * i]; y < Y[2 * i + 1]; ++y)
for (int z = Z[2 * i]; z < Z[2 * i + 1]; ++z)
occ[x][y][z] = true;//标记所有有长方体的区域，注意是左闭右开区间
vi Q;
Q.push_back(0);
occ[0][0][0] = -1;
while (!Q.empty()) {//从外围进行BFS，加一圈“空气”，用-1表示
int v = Q.back(); Q.pop_back();
int x = v & 0xFF, y = (v >> 8) & 0xFF, z = (v >> 16) & 0xFF;//此处的编码，解码技巧值得学习，但要注意此时每个数不能超过255
for (int d = 0; d < 6; ++d) {
int nx = x + dx[d], ny = y + dy[d], nz = z + dz[d];
if (nx >= 0 && ny >= 0 && nz >= 0 && nx < xn && ny < yn && nz < zn &&
!occ[nx][ny][nz]) {
occ[nx][ny][nz] = -1;
Q.push_back((nz << 16) | (ny << 8) | nx);
}
}
}
ll vol = 0, area = 0;
for (int x = 1; x < xn - 1; ++x)
for (int y = 1; y < yn - 1; ++y)
for (int z = 1; z < zn - 1; ++z) {
int sx = xv[x + 1] - xv[x], sy = yv[y + 1] - yv[y], sz = zv[z + 1] - zv[z];
if (occ[x][y][z] != -1) vol += (ll)sx*sy*sz;//该处存在方块，注意一定要写成“不等于-1”，因为此时内部的空气是0
for (int d = 0; d < 6; ++d)
if (occ[x][y][z] != -1 && occ[x + dx[d]][y + dy[d]][z + dz[d]] == -1)//点(x,y,z)处有方块，但延长一个单位方向后却是外围空气
area += dx[d] ? sy*sz : dy[d] ? sx*sz : sx*sy;
}
printf("%lld %lld\n", area, vol);
}
int main(void) {
int N;
for (scanf("%d", &N); N--; solve());
return 0;
}