首页 > 代码库 > UVa 12171 (离散化 floodfill) Sculpture
UVa 12171 (离散化 floodfill) Sculpture
题意：
三维空间中有n个长方体组成的雕塑，求表面积和体积。
分析：
我们可以在最外边加一圈“空气”，然后求空气的连通块的体积，最后用总体积减去即是雕塑的体积。
还有一个很“严重”的问题就是5003所占的空间太大，因此需要离散化。而在计算体积和表面积的时候要用原坐标。
离散化以后的坐标分别保存在xs、ys、zs，坐标为(x, y, z)的格子代表([xs[x], ys[y], zs[z]) ~ (xs[x+1], ys[y+1], zs[z+1]) 这一个小长方体。
这个题的难度对我来说属于大概思路比较明白，但是很多代码细节处理不好那种。
把节点和相关的函数封装在一个结构体里面是个狠不错的技巧，使编码思路清晰，代码可读性也很好。
1 #include <cstdio> 2 #include <algorithm> 3 #include <queue> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 50 + 5; 8 const int maxc = 1000 + 1; 9 10 int n, x0[maxn], y0[maxn], z0[maxn], x1[maxn], y1[maxn], z1[maxn]; 11 12 int nx, ny, nz; 13 int xs[maxn*2], ys[maxn*2], zs[maxn*2]; 14 15 const int dx[] = {1,-1,0,0,0,0}; 16 const int dy[] = {0,0,1,-1,0,0}; 17 const int dz[] = {0,0,0,0,1,-1}; 18 int color[maxn*2][maxn*2][maxn*2]; 19 20 struct Cell 21 { 22 int x, y, z; 23 Cell(int x=0, int y=0, int z=0):x(x), y(y), z(z) {} 24 bool valid() const { return x >= 0 && x < nx-1 && y >= 0 && y < ny-1 && z >= 0 && z < nz-1;} 25 bool solid() const { return color[x][y][z] == 1; } 26 bool getVis() const { return color[x][y][z] == 2; } 27 void setVis() const { color[x][y][z] = 2; } 28 Cell neighbor(int dir) const 29 { return Cell(x+dx[dir], y+dy[dir], z+dz[dir]); } 30 int volume() 31 { return (xs[x+1]-xs[x]) * (ys[y+1]-ys[y]) * (zs[z+1]-zs[z]); } 32 int area(int dir) 33 { 34 if(dx[dir]) return (ys[y+1]-ys[y]) * (zs[z+1]-zs[z]); 35 if(dy[dir]) return (xs[x+1]-xs[x]) * (zs[z+1]-zs[z]); 36 return (xs[x+1]-xs[x]) * (ys[y+1]-ys[y]); 37 } 38 }; 39 40 void discrectize(int* x, int& n) 41 { 42 sort(x, x + n); 43 n = unique(x, x + n) - x; 44 } 45 46 int ID(int* x, int n, int x0) 47 { 48 return lower_bound(x, x + n, x0) - x; 49 } 50 51 void floodfill(int& v, int& s) 52 { 53 v = s = 0; 54 Cell c; 55 c.setVis(); 56 queue<Cell> q; 57 q.push(c); 58 while(!q.empty()) 59 { 60 Cell c = q.front(); q.pop(); 61 v += c.volume(); 62 for(int i = 0; i < 6; ++i) 63 { 64 Cell c2 = c.neighbor(i); 65 if(!c2.valid()) continue; 66 if(c2.solid()) s += c.area(i); 67 else if(!c2.getVis()) 68 { 69 c2.setVis(); 70 q.push(c2); 71 } 72 } 73 } 74 v = maxc*maxc*maxc - v; 75 } 76 77 int main() 78 { 79 //freopen("in.txt", "r", stdin); 80 int T; 81 scanf("%d", &T); 82 while(T--) 83 { 84 memset(color, 0, sizeof(color)); 85 nx = ny = nz = 2; 86 xs[0] = ys[0] = zs[0] = 0; 87 xs[1] = ys[1] = zs[1] = maxc; 88 scanf("%d", &n); 89 for(int i = 0; i < n; ++i) 90 { 91 scanf("%d%d%d%d%d%d", &x0[i], &y0[i], &z0[i], &x1[i], &y1[i], &z1[i]); 92 x1[i] += x0[i]; y1[i] += y0[i]; z1[i] += z0[i]; 93 xs[nx++] = x0[i]; xs[nx++] = x1[i]; 94 ys[ny++] = y0[i]; ys[ny++] = y1[i]; 95 zs[nz++] = z0[i]; zs[nz++] = z1[i]; 96 } 97 discrectize(xs, nx); 98 discrectize(ys, ny); 99 discrectize(zs, nz);100 101 for(int i = 0; i < n; ++i)102 {103 int X1 = ID(xs, nx, x0[i]), X2 = ID(xs, nx, x1[i]);104 int Y1 = ID(ys, ny, y0[i]), Y2 = ID(ys, ny, y1[i]);105 int Z1 = ID(zs, nz, z0[i]), Z2 = ID(zs, nz, z1[i]);106 for(int X = X1; X < X2; X++)107 for(int Y = Y1; Y < Y2; ++Y)108 for(int Z = Z1; Z < Z2; ++Z)109 color[X][Y][Z] = 1;110 }111 112 int v, s;113 floodfill(v, s);114 printf("%d %d\n", s, v);115 }116 117 return 0;118 }
UVa 12171 (离散化 floodfill) Sculpture
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。