2013-12-28 12:20:48Morris
[数据结构与算法] 第13周 高级数据结构（1）
1:最近餐馆
- 描述
每到饭点，就又到了一日几度的小L纠结去哪吃饭的时候了。因为有太多太多好吃的地方可以去吃，而小L又比较懒不想走太远，所以小L会先找到距离他最近的M家餐馆然后再做筛选。
小L现在所在的位置和每家餐馆的位置用同一笛卡尔坐标系中的点表示，而点与点之间的距离为欧几里得距离，对于点p = (p1, p2,..., pn)和点q = (q1,q2,..., qn)，两者的距离定义如下
现给出在K维空间中小L所处的位置的坐标以及n个餐馆的位置，请帮助小L完成他的需求。
- 输入
- 第1行包含两个整数n和K，1≤n≤5000，1≤K≤5。
接下来n行，每行包含K个数，表示每个餐馆的坐标。
接下来1行，包含一个数t，1≤t≤10000，表示小L询问的数目。
每次询问包括两行。第1行包含K个数，表示小L所在的坐标。第2行包含一个数M，1≤M≤10。
所有坐标值不会超过10000。
输入数据包含多组数据，请逐个处理直到文件结束。 - 输出
- 对于每一个询问，输出m+1行：
第1行输出：”the closest M points are:”，其中M在输入中给出。
接下来M行输出距离最近的M家餐馆的坐标，按照由近及远的顺序输出。
输出数据保证答案唯一。保证从小L的位置到最近的M+1家餐馆位置各不相同，这说明如下输入数据：
2 2
1 1
3 3
1
2 2
1
不会存在。 - 样例输入
3 2 1 1 1 3 3 4 2 2 3 2 2 3 1
- 样例输出
the closest 2 points are: 1 3 3 4 the closest 1 points are: 1 3
對 x 取中點切割、分成兩個空間。
對 y 取中點切割、再分兩個空間。
.
.
.
對 x 取中點切割、分成兩個空間。
對 y 取中點切割、再分兩個空間。
...
搜尋最鄰近的 M 對時，努力地估價吧！
由於每次劃分的維度不同，要保留前幾次在某維度的估價情況。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct Node {
Node *l, *r;
int idx;
};
Node buf[5005];
int bufsize;
int pt[5005][5];
int L[5];
int n, t, K, M;
int i, j, k;
int A[5005];
int sortIdx;
bool cmp(int a, int b) {
return pt[a][sortIdx] < pt[b][sortIdx];
}
Node* build(int k, int l, int r) {
if(l > r)
return NULL;
sortIdx = k;
sort(A+l, A+r+1, cmp);
int m = (l + r)/2;
Node *ret = &buf[bufsize++];
ret->idx = A[m]; // point index
if(l != r) {
ret->l = build((k+1)%K, l, m-1);
ret->r = build((k+1)%K, m+1, r);
} else {
ret->l = ret->r = NULL;
}
return ret;
}
int max_dist = 0xfffffff;
int dist(int idx) {
int ret = 0;
for(int i = 0; i < K; i++)
ret += (pt[idx][i]-L[i])*(pt[idx][i]-L[i]);
return ret;
}
int toth(int h[]) {
int ret = 0;
for(int i = 0; i < K; i++)
ret += h[i];
return ret;
}
struct pQcmp {
bool operator() (int a, int b) {
return dist(a) < dist(b);
}
};
priority_queue<int, vector<int>, pQcmp> pQ;
void DC(Node *nd, int k, int h[]) {
if(nd == NULL || toth(h) >= max_dist)
return;
int d = dist(nd->idx);
if(d < max_dist) {
pQ.push(nd->idx);
if(pQ.size() == M+1) {
max_dist = dist(pQ.top());
pQ.pop();
}
}
int hk = h[k];
if(L[k] < pt[nd->idx][k]) {
if(nd->l != NULL)
DC(nd->l, (k+1)%K, h);
if(nd->r != NULL) {
h[k] = (pt[nd->idx][k] - L[k])*(pt[nd->idx][k] - L[k]);
DC(nd->r, (k+1)%K, h);
h[k] = hk;
}
} else {
if(nd->l != NULL) {
h[k] = (pt[nd->idx][k] - L[k])*(pt[nd->idx][k] - L[k]);
DC(nd->l, (k+1)%K, h);
h[k] = hk;
}
if(nd->r != NULL)
DC(nd->r, (k+1)%K, h);
}
}
void brute_force(int c[]) {
int d[5005];
for(i = 0; i < n; i++) {
d[i] = dist(i);
}
sort(d, d+n);
for(i = 0; i < M; i++) {
if(d[i] != dist(c[M-i-1]))
printf("[b] %d [m] %d\n", d[i], dist(c[M-i-1]));
}
}
int main() {
while(scanf("%d %d", &n, &K) == 2) {
for(i = 0; i < n; i++) {
for(j = 0; j < K; j++) {
scanf("%d", &pt[i][j]);
if(pt[i][j] < 0)
puts("wa");
}
A[i] = i;
}
bufsize = 0;
Node *root = build(0, 0, n-1);
scanf("%d", &t);
while(t--) {
for(i = 0; i < K; i++)
scanf("%d", &L[i]);
scanf("%d", &M);
max_dist = 2147483647;
int h[5] = {};
DC(root, 0, h);
printf("the closest %d points are:\n", M);
int buf[30], bidx = 0;
while(!pQ.empty()) {
int idx = pQ.top();
buf[bidx++] = idx;
pQ.pop();
}
//brute_force(buf);
for(i = bidx-1; i >= 0; i--) {
for(j = 0; j < K; j++) {
if(j) putchar(' ');
printf("%d", pt[buf[i]][j]);
}
puts("");
}
}
}
return 0;
}
2:四分树
- 描述
一幅如图2(a)所示的二进制图片常常会用一个二进制矩阵来表示。所谓二进制矩阵是指矩阵中的每一个数不是0就是1。图2(b)展示图2(a)用二进制矩阵表示的情况。
图2：(a)二进制图片(b)图片的矩阵表示(c)四分树划分(d)四分树表示
为了保存图2(b)这样的矩阵，经常使用四分树来完成。对于一个N * N的矩阵，N <= 512且N = 2^i（i为正整数），如果这个矩阵中的数不全一样，那么我们会把这个矩阵分成4个N/2 * N/2的矩阵，如图2(c)所示。之后，我们再对这4个N/2 * N/2的矩阵划分，同样地，如果里面的数不全一样则划分成N/4 * N/4的矩阵。图2(c)里面右边的两个N/2 * N/2的矩阵就被这样再度划分了。如此可以持续进行划分，直到里面的数全一样。图2(c)展示了完全划分完毕的样子。
我们一般都将二进制图片存成图2(d)这样的四分树的形式，这棵树是通过图2(c)里面的划分得到的。图2(d)里面的每一个结点都代表图2(c)里面的矩阵，而树的根结点代表整个大的矩阵。如果树中一个结点的值为1，则代表这个结点对应的矩阵需要划分成4个小矩阵。否则，这个结点将包含两个数。第一个数为0，表示不用再划分，第二个数为0或者1，表示整个矩阵都是这个值。整棵树可以用它的宽度优先遍历得到的结果来表示，如图2(d)中的树可以表示成(1)(0,0)(1)(0,1)(1)(0,0)(0,1)(1)(0,0)(0,0)(0,0)(0,1)(0,1)(0,0)(0,1)(0,0)(0,1)。删掉括号和逗号，我们可以得到一个更简短的纯二进制编码100101100011000000010100010001来编码这张图片，它的16进制形式为258C0511。
现在请你编写一个程序，求出给定图片的16进制形式的编码。
- 输入
- 第1行包含一个数k，1 <= k <= 100，表示数据的组数。
对于每一组数据，第1行包含一个数N表示图片的大小为N * N，其中N <= 512且N = 2^i（i为正整数）。
接下来跟着一个N * N的矩阵代表一张二进制图片。每两个0和1之间至少有一个空格。 - 输出
- 每张图片通过四分树得到的16进制编码。
- 样例输入
3 2 0 0 0 0 4 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 8 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- 样例输出
0 114 258C0511
- #include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int g[512][512];
int tree[1048576+5];
char code[1048576], *codeptr;
int dfs(int k, int lx, int rx, int ly, int ry) {
if(lx > rx || ly > ry) return 0;
if(lx == rx && ly == ry) {
tree[k] = g[lx][ly];
return g[lx][ly];
}
int mx = (lx + rx)/2;
int my = (ly + ry)/2;
int s = 0;
s += dfs((k<<2), lx, mx, ly, my);
s += dfs((k<<2)+1, lx, mx, my+1, ry);
s += dfs((k<<2)+2, mx+1, rx, ly, my);
s += dfs((k<<2)+3, mx+1, rx, my+1, ry);
tree[k] = s;
return s;
}
void bfs(int k, int lx, int rx, int ly, int ry) {
queue<int> K, W, H;
K.push(k), W.push(rx-lx+1), H.push(ry-ly+1);
int h, w;
while(!K.empty()) {
k = K.front(), K.pop();
w = W.front(), W.pop();
h = H.front(), H.pop();
if(tree[k] == w*h || tree[k] == 0) {
*codeptr++ = '0';
*codeptr++ = (tree[k] != 0) + '0';
continue;
}
*codeptr++ = '1';
K.push(k<<2), W.push(w/2), H.push(h/2);
K.push((k<<2)+1), W.push(w/2), H.push(h/2);
K.push((k<<2)+2), W.push(w/2), H.push(h/2);
K.push((k<<2)+3), W.push(w/2), H.push(h/2);
}
}
int main() {
int testcase;
int n;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d", &g[i][j]);
int f = dfs(1, 0, n-1, 0, n-1);
codeptr = code;
bfs(1, 0, n-1, 0, n-1);
*codeptr = '\0';
int len = strlen(code), counter = len%4;
int output = 0;
if(counter == 0) counter = 4;
//printf("%s\n", code);
for(i = 0; i < len; i++) {
output = output<<1 | (code[i]-'0');
if(--counter == 0) {
printf("%X", output);
output = 0;
counter = 4;
}
}
puts("");
}
return 0;
}