UVa 297 - Quadtrees 四叉树, 及其在编码图像的应用

297-Quadtrees

4898

41.55%

1811

90.39%

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=233

题目类型： 数据结构， 二叉树

题意与背景：

同二叉树一样，四叉树也是一种数据结构，是一种每个节点最多有四个子树的数据结构。

一个四叉树是可以表示格式用于编码图像。背后的基本思想是, 任何图像可以分为四个象限，每个象限也可以再次被分割成4个亚象限,等等。因此四叉树是在二维图片中定位像素的唯一适合的算法。

当然， 如果一整幅图只有一种一种颜色，那么可以只用一个单一的节点表示。一般来说， 如果图片的像素的不同颜色组成，那么每个象限只需要再被细分下去。因此,四叉树不需要统一的深度。

现代计算机艺术家在黑白图像32*32单元下工作， 每幅图像总计有1024像素。其中一个需要执行的操作是添加两个图像，把它们合并形成一个新形象。两幅图像合并，在相对应的象限的像素中，只要一副中是黑色的，那么合并后该像素就是黑色的，否则就是白色的。

例如：

样例输入：

3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe

样例输出：

There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.

分析：

题目就是分别给出关于两幅图在四叉树数据结构中的表示的按照前序遍历得到的序列， 然后要求我们求出合并后的图像的黑色像素有多少个。

其中，p代表是一个父节点(parent)，f表示表示该节点是黑色的(full), e 表示该节点是白色的(empty).

我的方法是，首先， 需要按照所给的序列构造出两幅图的四叉树，可以通过递归的方法进行构造，和构造二叉树十分像。

然后，就是对两棵树进行计算的过程。具体是下面的代码

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str1[100005], str2[100005];

class Node{
public:
    char data;
    Node *son[4];
};
Node node[20000];
int nIndex, pos1,pos2, sum;
inline Node* NewNode(){
    node[nIndex].data = 0;
    for(int i=0; i<4; ++i) node[nIndex].son[i] = NULL;
    return &node[nIndex++];
}
// 通过序列建树
Node *BuildTree(Node* root, int &pos, char *str){
    ++pos;
    if( pos==strlen(str) ) return NULL;
    root = NewNode();
    root->data=str[pos];
    if(str[pos]=='p') {
        for(int i=0; i<4; ++i){
            if(root->son[i]==NULL){
                root->son[i] = BuildTree(root->son[i], pos, str);
            }
        }
    }
    return root;
}
// 用深搜遍历两棵树求出合并后的黑色像素个数
void dfs(Node *root1, Node *root2, int level){
   if(!root1 && !root2) return ;

    if(!root1){
        if(root2->data=='f'){
            sum += 1024>>(level*2);
            return;
        }
        for(int i=0; i<4; ++i)
            dfs(root1, root2->son[i], level+1);
        return;
    }
      if(!root2){
        if(root1->data=='f'){
            sum += 1024>>(level*2);
            return;
        }
        for(int i=0; i<4; ++i)
            dfs(root1->son[i],root2, level+1);
        return;     
    }
    if(root1->data=='f' || root2->data=='f'){
        sum += 1024>>(level*2);
        return ;
    }
    
    for(int i=0; i<4; ++i)
        dfs(root1->son[i], root2->son[i], level+1); 
}

void output(Node *root){
    if(root){
        printf("%c",root->data);
        for(int i=0; i<4; ++i)
            output(root->son[i]);
    }
}

void Solve(){
    Node *root1=NULL, *root2=NULL;
    pos1=-1, pos2=-1;
    nIndex=0;
    root1 = BuildTree(root1,pos1, str1);
    root2 = BuildTree(root2,pos2, str2);
    sum = 0;
    dfs(root1, root2 ,0);
    printf("There are %d black pixels.\n", sum);
}

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int T;
    scanf("%d%*c",&T);
    while(T--){
        scanf("%s %s", str1,str2);
        Solve();
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double