6 11_quadtrees_uva297 - nuaazdh/acm GitHub Wiki
##例题6-11 四叉树(Quadtrees UVa297) ###问题
对一个32x32像素的图形,切成四份,右上角开始逆时针标上1,2,3,4块,每个像素点只有黑色(f,full)和白色(e,empty)。可以用四叉树来表示出这个图形。其中p表示该块不是纯黑色或者纯白色,即四叉树的非叶子结点。 按照先序遍历给出两个四叉树,求所表示的图像合并以后,黑色像素点的数目。 第一行为测试用例的个数。
样例输入
3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe
样例输出
There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.
###分析
首先想到如何合并这个树,可以对对两个树分别展开,方法如下,遍历两个树,如果两个都不是 p
,则继续,如果两个都是p
,继续,否则,一个是p
,另一个是f
,则将f展开为 pffff
,然后再逐个比较,知道展开的两个树等长度,即可进行合并操作。
合并以后,还得递归求解合并以后的黑色像素点数目,开始的权重认为是 32x32,后面每次遇到一层的p, 权值都变为原来四分之一。
###code in C++
#include <stdio.h>
#include <string.h>
#define MAX_LEN 2048
char tree1[MAX_LEN];
char tree2[MAX_LEN];
char conbine_tree[MAX_LEN];
int get_pixel(int &pos, int weight) {
int cnt, total = 0;
if (pos > strlen(conbine_tree))
return 0;
if (conbine_tree[pos] == 'f') {
pos++;
total += weight;
} else if (conbine_tree[pos] == 'p') {
cnt = 4;
while (cnt--) {
++pos;
if (conbine_tree[pos] == 'f') {
total += weight/4;
}else if(conbine_tree[pos] == 'p'){
total += get_pixel(pos, weight/4);
}else{
}
}
} else {
pos++;
}
return total;
}
int main() {
int T, len1, len2, i, j, pos, pcnt;
scanf("%d", &T);
while (T--) {
scanf("%s", tree1);
scanf("%s", tree2);
len1 = strlen(tree1);
len2 = strlen(tree2);
memset(conbine_tree, 0, sizeof(conbine_tree));
i = j = pos = 0;
while (i < len1 && j < len2) {
if ((tree1[i] == 'p' && tree2[j] == 'p')) {
conbine_tree[pos++] = 'p';
++i;
++j;
continue;
}
if (tree1[i] != 'p' && tree2[j] != 'p') {
if (tree1[i] == 'f' || tree2[j] == 'f') {
conbine_tree[pos++] = 'f';
} else {
conbine_tree[pos++] = 'e';
}
++i;
++j;
} else if (tree1[i] == 'p' && tree2[j] != 'p') {
if (tree2[j] == 'f') {
conbine_tree[pos++] = tree2[j++];
pcnt = 4;
++i;
while (pcnt > 0) {
if (tree1[i] != 'p') {
--pcnt;
}
else {
pcnt += 4;
}
++i;
}
} else {
j++;
conbine_tree[pos++] = tree1[i++];
pcnt = 4;
while (pcnt > 0) {
if (tree1[i] != 'p') {
--pcnt;
}
else {
pcnt += 4;
}
conbine_tree[pos++] = tree1[i++];
}
}
} else if (tree2[j] == 'p' && tree1[i] != 'p') {
if (tree1[i] == 'f') {
conbine_tree[pos++] = tree1[i++];
pcnt = 4;
++j;
while (pcnt > 0) {
if (tree2[j] != 'p') {
--pcnt;
}
else {
pcnt += 4;
}
++j;
}
} else {
++i;
conbine_tree[pos++] = tree2[j++];
pcnt = 4;
while (pcnt > 0) {
if (tree2[j] != 'p') {
--pcnt;
}
else {
pcnt += 4;
}
conbine_tree[pos++] = tree2[j++];
}
}
}
}
if (i < len1) {
while (i < len1) conbine_tree[pos++] = tree1[i++];
} else {
while (j < len2) conbine_tree[pos++] = tree2[j++];
}
pos = 0;
printf("There are %d black pixels.\n",get_pixel(pos,1024));
}
return 0;
}
###点评
- 一个AC的解答,但是代码比较冗余。
- 有没有改进的办法了?