题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=233
首先建树，建树的同时算出每个节点的pixels，然后分3种情况递归求解：1、两个都为叶节点；2、有且只有一个为叶节点；3、都不是叶节点。由于每个节点记录了pixels，所以对于情况1、2可以直接返回结果。
#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 阅读(420)
评论(0) 编辑 收藏 引用 所属分类:
数据结构