| Quadtrees |
A quadtree is a representation format used to encode images. The fundamental idea behind the quadtree is that any image can be split into four quadrants. Each quadrant may again be split in four sub quadrants, etc. In the quadtree, the image is represented by a parent node, while the four quadrants are represented by four child nodes, in a predetermined order.
Of course, if the whole image is a single color, it can be represented by a quadtree consisting of a single node. In general, a quadrant needs only to be subdivided if it consists of pixels of different colors. As a result, the quadtree need not be of uniform depth.
A modern computer artist works with black-and-white images of
units, for a total of 1024 pixels per image. One of the operations he performs is adding two images together, to form a new image. In the resulting image a pixel is black if it was black in at least one of the component images, otherwise it is white.
This particular artist believes in what he calls the preferred fullness: for an image to be interesting (i.e. to sell for big bucks) the most important property is the number of filled (black) pixels in the image. So, before adding two images together, he would like to know how many pixels will be black in the resulting image. Your job is to write a program that, given the quadtree representation of two images, calculates the number of pixels that are black in the image, which is the result of adding the two images together.
In the figure, the first example is shown (from top to bottom) as image, quadtree, pre-order string (defined below) and number of pixels. The quadrant numbering is shown at the top of the figure.
Input Specification
The first line of input specifies the number of test cases (N) your program has to process.
The input for each test case is two strings, each string on its own line. The string is the pre-order representation of a quadtree, in which the letter 'p' indicates a parent node, the letter 'f' (full) a black quadrant and the letter 'e' (empty) a white quadrant. It is guaranteed that each string represents a valid quadtree, while the depth of the tree is not more than 5 (because each pixel has only one color).
Output Specification
For each test case, print on one line the text 'There are X black pixels.', where X is the number of black pixels in the resulting image.
Example Input
3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe Example Output
There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels. 分析：各層像素點是如何計算的？根據題意，一張完整的圖有1024個像素點，那麼第一層的每個結點有1024/1=1024個像素點，第二層每個結點有1024/4=256個像素點（因為第二層有4個結點），第三層每個結點有256/4=64個結點...依次類推。是以以下執行個體的計算方法是：
1*256+3*64=448；1*256+1*64=320 ；2*256+2*64=640；
思路：分别建立兩個圖像樹，将相同層次相同位置的樹的結點按規則相加（即和并兩顆樹），前序周遊樹的思想周遊合并後的樹（在周遊的同時找到黑色結點，并根據深度計算此結點的像素點數，累加到一個變量中）。需要注意的地方：不同深度上的黑色結點代表的像素點數不同。
代碼：
#include <iostream>
#include <string>
#include <queue>
using namespace std;
typedef struct tree{
char c;
struct tree *cnode1,*cnode2,*cnode3,*cnode4;
}Tree;
Tree *create_node(char c)
{
Tree *node=new Tree;
node->c=c;
node->cnode1=node->cnode2=node->cnode3=node->cnode4=NULL;
return node;
}
Tree *create_tree(Tree *root,const string pre_exp,size_t &start)
{//根據字首表達式建立樹
if(start>=pre_exp.size()) return NULL;
Tree *node=create_node(pre_exp[start]);
if(root==NULL) root=NULL;
if(node->c=='p'){
node->cnode1=create_tree(root,pre_exp,++start);//遞歸建立第一個子節點
node->cnode2=create_tree(root,pre_exp,++start);//遞歸建立第二個子節點
node->cnode3=create_tree(root,pre_exp,++start);//遞歸建立第三個子節點
node->cnode4=create_tree(root,pre_exp,++start);//遞歸建立第四個子節點
}
return node;
}
void delete_child(Tree *t)
{//釋放樹空間
if(t){
delete_child(t->cnode1);
delete_child(t->cnode2);
delete_child(t->cnode3);
delete_child(t->cnode4);
delete t;
t=NULL;
}
}
Tree *merge(Tree *root1,Tree *root2)
{//将樹root2合并到root1
queue<Tree *> que1,que2;
Tree *p1=NULL,*p2=NULL;
que1.push(root1);que2.push(root2);
while(!que1.empty() && !que2.empty()){//兩顆樹對應的結點進行合并，如根節點與根節點合并，root1第一個子結點與root2第一個子節點合并，需要一一對應
p1=que1.front();p2=que2.front();
que1.pop();que2.pop();
if((p1->c=='p') && (p2->c=='p')) {
que1.push(p1->cnode1);
que1.push(p1->cnode2);
que1.push(p1->cnode3);
que1.push(p1->cnode4);
que2.push(p2->cnode1);
que2.push(p2->cnode2);
que2.push(p2->cnode3);
que2.push(p2->cnode4);
delete p2;//釋放空間
}
else if(p1->c=='p' && p2->c=='f'){
p1->c='f';
delete_child(p1->cnode1);
delete_child(p1->cnode2);
delete_child(p1->cnode3);
delete_child(p1->cnode4);
p1->cnode1=p1->cnode2=p1->cnode3=p1->cnode4=NULL;
delete p2;
}
else if(p1->c=='e' && p2->c=='f'){
p1->c='f';
delete p2;
}
else if(p1->c=='e' && p2->c=='p'){
p1->c='p';
p1->cnode1=p2->cnode1;
p1->cnode2=p2->cnode2;
p1->cnode3=p2->cnode3;
p1->cnode4=p2->cnode4;
}
else {
delete p2;
}
}
return root1;
}
int get_depth_pile(int depth)
{//根據結點深度擷取該層次應該具有的像素數
int pixels=1024;
for(int i=1;i<depth;++i){
pixels=pixels/4;
}
return pixels;
}
void black_pile(Tree *t,int &pixels,int depth)
{//前序周遊計算黑色像素數
if(t){
++depth;
if(t->c=='f'){
pixels+=get_depth_pile(depth);
}
black_pile(t->cnode1,pixels,depth);
black_pile(t->cnode2,pixels,depth);
black_pile(t->cnode3,pixels,depth);
black_pile(t->cnode4,pixels,depth);
}
}
void pre_travel(Tree *t)
{//測試用
if(t){
cout<<t->c;
pre_travel(t->cnode1);
pre_travel(t->cnode2);
pre_travel(t->cnode3);
pre_travel(t->cnode4);
}
}
int main()
{
int num;
cin>>num;
while(num--){
string exp1,exp2;
while(cin>>exp1>>exp2){
size_t start=0;
Tree *root1=NULL,*root2=NULL;
root1=create_tree(root1,exp1,start);//建立第一張圖像樹
start=0;
root2=create_tree(root2,exp2,start);//建立第二章圖像樹
Tree *root=merge(root1,root2);
int pixels=0;
black_pile(root,pixels,0);
cout<<"There are "<<pixels<<" black pixels."<<endl;
delete_child(root);//釋放樹空間
// pre_travel(root);
// cout<<"\n--------------------------"<<endl;
}
}
return 0;
}
/*
1
ppeeefpffeefe
pefepeefe
*/