随笔-68  评论-10  文章-0  trackbacks-0
题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=233 

首先建树,建树的同时算出每个节点的pixels,然后分3种情况递归求解:1、两个都为叶节点;2、有且只有一个为叶节点;3、都不是叶节点。由于每个节点记录了pixels,所以对于情况12可以直接返回结果。

#include <iostream>
#include 
<string>
using namespace std;

struct quadtree
{
    
int val;
    quadtree 
*t[4];
    quadtree()
    
{
        val 
= 0;
        
for(int i = 0; i < 4++i) t[i] = 0;
    }

    quadtree(
int v)
    
{
        val 
= v;
        
for(int i = 0; i < 4++i) t[i] = 0;
    }

    
bool isLeaf()
    
{
        
return !(t[0|| t[1|| t[2|| t[3]);
    }

    
~quadtree()
    
{
        
for(int i = 0; i < 4++i)
        
if(t[i]) delete t[i];
    }

}
;

quadtree
* build(const string &s, int &idx, int pixel)
{
    
if(s[idx] == 'e')
    
{
        
++idx;
        
return new quadtree;
    }

    
else if(s[idx] == 'f')
    
{
        
++idx;
        
return new quadtree(pixel);
    }

    
else// if(s[idx] == 'p')
    {
        
++idx;
        quadtree 
*tree = new quadtree;
        
for(int i = 0; i < 4++i)
        
{
            tree
->t[i] = build(s, idx, pixel / 4);
            tree
->val += tree->t[i]->val;
        }

        
return tree;
    }

}


int merge_tree(quadtree *t1, quadtree *t2)
{
    
if(t1->isLeaf() && t2->isLeaf())
    
return t1->val ? t1->val : t2->val;
    
else if(t1->isLeaf() && !t2->isLeaf())
    
return t1->val ? t1->val : t2->val;
    
else if(!t1->isLeaf() && t2->isLeaf())
    
return t2->val ? t2->val : t1->val;
    
else
    
{
        
int ans = 0;
        
for(int i = 0; i < 4++i)
        
{
            ans 
+= merge_tree(t1->t[i], t2->t[i]);
        }

        
return ans;
    }

}


int main()
{
    
int T;
    
string s1, s2;
    quadtree 
*tree_head1, *tree_head2;
    cin 
>> T;
    
while(T--)
    
{
        cin 
>> s1 >> s2;
        
int idx = 0;
        tree_head1 
= build(s1, idx, 1024);
        idx 
= 0;
        tree_head2 
= build(s2, idx, 1024);
        
int ans = merge_tree(tree_head1, tree_head2);
        cout 
<< "There are " << ans << " black pixels." << endl;
        
if(tree_head1) delete tree_head1;
        
if(tree_head2) delete tree_head2;
    }

    
return 0;
}



posted on 2011-11-25 21:22 wuxu 阅读(399) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理