首页 > 代码库 > UVa Sculpture(离散化 floodfill)
UVa Sculpture(离散化 floodfill)
题意：
给定n个立方体的一个顶点坐标和3边长度， 问这些立方体组成的雕塑的表面积和体积， 坐标都是整数，n最大为50， 最大为500， 边长最大也是500。
分析：
继UVa221后又一道离散化
首先先深入理解一下离散化： （转自 http://www.cnblogs.com/jerryRey/p/4599388.html）
先来看一个问题：给你以下的网格，你需要多少空间去存储红点区间的信息呢？
只需要图上所示的1，2，3，4个点就足够表示红点所在区间了，为什么不是一个区间的第一个红点和最后一个红点呢？（如果这样记录的话则必须加一区间点，记录区间内部信息，因为端点可能是两个区间的交集而区间内可能只被操作了一次）这样做的好处是空白区域的长度也能轻易计算出来。
因此离散化的核心在于以点代表区间。
对于本题， 如果直接建一个1000*1000*1000的数组进行floodfill ， 方法是可行的， 但是从数据上看可能会爆内存+超时， 因为这里数据规模已经到了1e9.
所以我们需要离散化出我们要用的坐标， 对于50个立方体来说， 我们每一个维度（xyz）最大会有50*2 = 100个不同的坐标， 那么我们就可以把这些坐标的区间段记录下来， 这些区间段的性质都是一样的（要么没有东西， 要么是立方体）， 所以我们就可以把一个区间离散化为一个点， 然后将这些点填入一个100*100*100的数组做floodfill （数据规模1e6)。
因为本题还有有很多细节的地方， 所以我没有独立编程去实现， 贴一个对刘汝佳代码注释过的代码。
1 #include<cstdio>
2 #include<cstring>
3 #include<queue>
4 #include<algorithm>
5 using namespace std;
6 const int maxn = 50 +5 ;
7 const int maxc = 1000 + 1;
8
9 //原来的数据
10 int n, x0[maxn], x1[maxn], y0[maxn], y1[maxn], z0[maxn], z1[maxn];
11
12 //离散化 （将每个线段离散为一个点）
13 int nx, ny, nz;
14 int xs[maxn*2], ys[maxn*2], zs[maxn*2];
15
16 //六个方向 如果是xz面看的话 就是 右左前后上下
17 const int dx[] = {1,-1,0,0,0,0};
18 const int dy[] = {0,0,1,-1,0,0};
19 const int dz[] = {0,0,0,0,1,-1};
20
21 //离散化数组，每一个点都是代表原来的一个线段（不一定是原来的矩形， 可能是矩形的一部分）， 在这个坐标内floodfill
22 int color[maxn*2][maxn*2][maxn*2];
23
24 //
25 struct cube{
26 int x, y, z; //只要有xyz这个点 ， 就能在color数组内对应空气或者实体
27 cube(int x = 0, int y = 0, int z = 0): x(x) , y(y) , z(z){}
28 bool valid() const{
29 //每个点的左闭右开区间代表一个线段， 而且最后一个点就是范围极限（它不代表一个线段）， 所以范围应该是[0, 最后一个点的前一个]
30 //下标从0开始 一直到 nx - 1 个点
31 return x >= 0 && x < nx - 1 && y >= 0 && y < ny-1 && z>=0 && z < nz -1;
32 }
33
34 bool solid() const{
35 //判断这个点代表的是空气还是实体
36 return color[x][y][z] == 1;
37 }
38
39 bool getvis() const{
40 //判断是否被访问过
41 return color[x][y][z] == 2;
42 }
43
44 void setvis() const{
45 color[x][y][z] = 2;
46 }
47 //访问他的邻居 访问要先判断是否 valid
48 cube neighbor(int dir) const{
49 return cube(x+dx[dir], y+dy[dir], z+dz[dir]);
50 }
51 int volume() const{
52 //要计算这个color点的体积， 要重新找回这个color点原始的数据
53 return (xs[x+1] - xs[x]) * (ys[y+1] -ys[y]) * (zs[z+1]-zs[z]);
54 }
55 int area(int dir) const{//计算表面积
56 //想象一下 如果遍历过程中向上碰到solid， 那么说明这肯定是一个 xy型的面， 所以可以加上x*y
57 if(dx[dir] != 0) return (ys[y+1] - ys[y]) * (zs[z+1]-zs[z]);
58 else if(dy[dir] != 0) return (xs[x+1] - xs[x]) * (zs[z+1] - zs[z]);
59 return (xs[x+1] - xs[x]) * (ys[y+1] - ys[y]);
60 }
61 };
62
63 void discretize(int* x, int& n){
64 sort(x,x+n); //默认升序
65 n = unique(x,x+n) - x; // 这样就可以求出有多少个不同的元素
66 }
67 int ID(int* x, int n, int x0){//使原来矩形的数据对应离散化数组的下标
68 return lower_bound(x, x+n, x0) - x; //返回一个等于x0的下标
69 }
70
71 void floodfill(int&v , int& s){
72 v = 0;
73 s = 0;
74 cube c;
75 c.setvis();
76 queue<cube> q;//碰到空气就入队， 碰到solid计算表面积
77 q.push(c);
78 while(!q.empty()){
79 cube c = q.front(); q.pop();
80 v += c.volume(); //出队空气的体积
81 for(int i = 0; i < 6; i++){
82 cube c2 = c.neighbor(i);
83 if(!c2.valid()) continue;
84 if(c2.solid()) s += c.area(i);
85 else if(!c2.getvis()){
86 c2.setvis();
87 q.push(c2);
88 }
89 }
90 }
91 v = maxc*maxc*maxc - v;
92 }
93
94 int main(){
95 int T;
96 scanf("%d", &T);
97 while(T--){
98 nx = ny = nz = 2;
99 xs[0] = ys[0] = zs[0] = 0;//给定下界 让空气可以严格包围矩形
100 xs[1] = ys[1] = zs[1] = maxc; // 同上
101
102 scanf("%d", &n);
103 for(int i = 0; i < n ;i++){
104 scanf("%d %d %d %d %d %d", &x0[i], &y0[i], &z0[i], &x1[i], &y1[i], &z1[i]);
105 x1[i] += x0[i], y1[i] += y0[i], z1[i] += z0[i];
106
107 xs[nx++] = x0[i], xs[nx++] = x1[i];
108 ys[ny++] = y0[i], ys[ny++] = y1[i];
109 zs[nz++] = z0[i], zs[nz++] = z1[i];
110 }
111 discretize(xs,nx);//离散化， 传入一个数组坐标和一个应用变量， 去重输出有多少段
112 discretize(ys,ny);
113 discretize(zs,nz);
114 memset(color, 0, sizeof(color));//初始化color 准备用坐标填入
115 for(int i = 0; i < n; i++){
116 int X1 = ID(xs,nx,x0[i]), X2 = ID(xs,nx,x1[i]);
117 int Y1 = ID(ys,ny,y0[i]), Y2 = ID(ys,ny,y1[i]);
118 int Z1 = ID(zs,nz,z0[i]), Z2 = ID(zs,nz,z1[i]);
119 //左开右闭区间代表线段
120 for(int X = X1; X < X2; X++){
121 for(int Y = Y1; Y < Y2; Y++){
122 for(int Z = Z1; Z < Z2; Z++){
123 color[X][Y][Z] = 1;
124 }
125 }
126 }
127 }
128 int v, s;
129 floodfill(v, s);
130 printf("%d %d\n",s,v);
131 }
132 }
UVa Sculpture(离散化 floodfill)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。