UVA 12171

Posted on | In , | Visitors:

This is my blog.
今天又犯了一个老错误
早上不怎么想起床
做了一套四级卷子
为了吃饭（居然是这个理由）
出门自习了
看到一道好题
嗯 思维很重要

我就不写什么废话了，直接说这题的精髓吧！

小记

  1. 反面思考
    求体积，即总体积-空气体积。需要外围加一圈。这个思路和UVA-1103是相同的。感觉这个想法可以用在很多图的问题中，可以积累下来。
  2. 离散化
    由于个数n很小，而x,y,z的差距可能很大，这时候离散化可以减少空间。而因为在这题中我们会用到bfs，这样就会超时了。
  3. floodfill
    这个搜了一下貌似不是算法，其实也就是结合了bfs，发现一般bfs比dfs更优（就是一种感觉，以后我写题估计会先考虑使用bfs。虽然感觉dfs更好想。
  4. 模块化
    等会放出我觉得很好的代码，很清晰。而且模块化，功能化。值得学习。
  5. unique
    在STL中unique函数是一个去重函数， unique的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除，是把重复的元素移到后面去了，然后依然保存到了原数组中，然后 返回去重后最后一个元素的地址，因为unique去除的是相邻的重复元素，所以一般用之前都会要排一下序。
  6. 结构体
    1
    2
    3
    4
    5
    6
    7
    struct Point{
        int x,y,z;
        Point(int _x,int _y,int _z){
            x=_x;y=_y;z=_z;
        }
        Point(){}
    }p[maxn];

其实这一段代码我不是第一次接触到了，但还是想拿上来。很好用，很常用。

  1. 左闭右开填格子

AC代码代码源处

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 105;
const int maxr = 1005;
int dx[] = {1,-1, 0, 0, 0, 0};
int dy[] = {0, 0, 1,-1, 0, 0};
int dz[] = {0, 0, 0, 0, 1,-1};
struct Point{
    int x, y, z;
    Point(int x, int y, int z): x(x), y(y), z(z){}
    Point(){}
};
Point p[maxn];
int x[maxn], y[maxn], z[maxn];        //离散化后的坐标轴
int a[maxn][maxn][maxn];            //离散坐标系
int vis[maxn][maxn][maxn];            //标记是否访问
int n, nx, ny, nz;                    //数据量以及离散坐标轴的长度
int v, s;
void input();                                    //输入
void build();                                    //填格子
void bfs();                                        //广搜求 v 和 s
int getArea(int tx, int ty, int tz, int dir);    //计算 tx ty tz 长方体在 dir 方向上的面积（与空气的接触面积）
int main(){
    //freopen("input.txt", "r", stdin);
    int T;
    cin >> T;
    while(T--){
        input();
        build();
        bfs();
        cout << s << " " << v << endl;
    }
}
void input(){
    memset(a, 0, sizeof(a));
    memset(vis, 0, sizeof(vis));
    v = 0;    s = 0;
    cin >> n;
    for(int i=1; i<=2*n; i+=2){
        cin >> p[i].x    >> p[i].y    >> p[i].z;
        cin >> p[i+1].x    >> p[i+1].y    >> p[i+1].z;
        p[i+1].x += p[i].x;
        p[i+1].y += p[i].y;
        p[i+1].z += p[i].z;        //算出坐标
        x[i] = p[i].x;        y[i] = p[i].y;        z[i] = p[i].z;
        x[i+1] = p[i+1].x;    y[i+1] = p[i+1].y;    z[i+1] = p[i+1].z;
    }
    x[0] = 0;             y[0] = 0;              z[0] = 0;
    //将坐标轴排序去重
    sort(x, x+2*n+1);
    sort(y, y+2*n+1);
    sort(z, z+2*n+1);
    //在STL中unique函数是一个去重函数， unique的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除，是把重复的元素移到后面去了，然后依然保存到了原数组中，然后 返回去重后最后一个元素的地址，因为unique去除的是相邻的重复元素，所以一般用之前都会要排一下序。
    nx = unique(x, x+2*n+1) - x;
    ny = unique(y, y+2*n+1) - y;
    nz = unique(z, z+2*n+1) - z;
    //在周围围上空气
    x[nx++] = maxr;        y[ny++] = maxr;     z[nz++] = maxr;
}
void build(){
    for(int i=1; i<=2*n; i++){
        int x1, x2, y1, y2, z1, z2;        //长方体在离散化后的坐标系中的位置
        x1 = lower_bound(x, x+nx, p[i].x) - x;
        x2 = lower_bound(x, x+nx, p[i+1].x) - x;
        y1 = lower_bound(y, y+ny, p[i].y) - y;
        y2 = lower_bound(y, y+ny, p[i+1].y) - y;
        z1 = lower_bound(z, z+nz, p[i].z) - z;
        z2 = lower_bound(z, z+nz, p[i+1].z) - z;
        for(int i=x1; i<x2; i++)    //左闭右开区间填格子
            for(int j=y1; j<y2; j++)
                for(int k=z1; k<z2; k++)
                    a[i][j][k] = 1;
    }
}
void bfs(){
    queue<Point> q;
    q.push(Point(0, 0, 0));
    vis[0][0][0] = 1;
    while(!q.empty()){
        Point t = q.front();    q.pop();
        //如果这一点为空气，则累加空气体积
        if(a[t.x][t.y][t.z] == 0)
            v += (x[t.x+1] - x[t.x]) * (y[t.y+1] - y[t.y]) * (z[t.z+1] - z[t.z]);
        for(int i=0; i<6; i++){
            int tx, ty, tz;        //与 t 点相邻的点
            tx = t.x + dx[i];
            ty = t.y + dy[i];
            tz = t.z + dz[i];
            if(tx<0 || tx>=nx-1 || ty<0 || ty>=ny-1 || tz<0 || tz>=nz-1)    //过滤掉出界的情况
                continue;
            if(a[tx][ty][tz] == 1){        //为长方体，则计算接触面积并累加
                s += getArea(tx, ty, tz, i);
            }else if(a[tx][ty][tz] == 0 && vis[tx][ty][tz] == 0){        //为空气并且没访问过，则加入队列
                q.push(Point(tx, ty, tz));
                vis[tx][ty][tz] = 1;
            }
        }
    }
    v = maxr*maxr*maxr - v;
}
int getArea(int tx, int ty, int tz, int dir){
    //不同方向的接触面，面积不同
    if(dx[dir] != 0){
        return (y[ty+1]-y[ty]) * (z[tz+1]-z[tz]);
    }else if(dy[dir] != 0){
        return (x[tx+1]-x[tx]) * (z[tz+1]-z[tz]);
    }else{
        return (x[tx+1]-x[tx]) * (y[ty+1]-y[ty]);
    }
}

其他

多组数据的时候一定要考虑很多事情，比如初始化，比如模块化，比如必须读入完后才可以输出……

转载请注明出处，谢谢。

愿 我是你的小太阳


买糖果去喽