題目意思：給定兩個字符串，字符p對應建立子樹，字符e為白色，f為黑色對於不同層黑點f對應不同的值，最上面為1024下來為每個子樹256.....，這樣建立兩顆四叉樹，計算兩顆樹相加後的黑點f對應的值，注意在兩顆樹上同一點處，只要有一個為黑點，那麼相加後就為黑點
解題思路：1首先建立兩顆樹，采用遞歸建樹的方法 2建完樹後利用前序遍歷的方法進行遞歸求解和
代碼：
[cpp]
<span style="font-size:18px;">#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <deque>
#include <algorithm>
using namespace std;
const int MAXN = 1000010;//定義一個常量
//4叉樹的結構體
struct Btree{
char c;
struct Btree *child[4];//四叉我們開個數組存儲四個子樹
};
Btree *root1 , *root2;//兩顆樹的根節點
char str1[MAXN] , str2[MAXN];//存儲讀入的兩串字符串
int l1 , l2 , sum , pos;
//4叉樹的初始華
void newnode(Btree *u){
u -> c = 0;
for(int i = 0 ; i < 4 ; i++)
u -> child[i] = NULL;
}
//樹的遞歸建立
Btree* BuildTree(Btree *root , char *str){//返回Btree*
++pos;//pos要為全局，注意遞歸的全局和局部變量區別
if(pos == strlen(str))//如果達到字符串末尾則返回NULL
return NULL;
root = new Btree;//每一New一個
newnode(root);//new出來要習慣初始化
root -> c = str[pos];//根節點的值為str[pos]
if(str[pos] == 'p'){//如果為p則建立子樹，否則直接返回根節點就好
for(int i = 0 ; i < 4 ; ++i){
if(root->child[i] == NULL){//如果哪個子樹為空則遞歸產生子樹
root->child[i] = BuildTree(root->child[i] , str);
}
}
}
return root;
}
//前序求和（同時遍歷兩顆樹）
void preorder(Btree *root1 , Btree *root2 , int level){
if(root1 == NULL && root2 == NULL)//如果兩顆樹此時都為空則直接返回
return;
if(root1 == NULL){//樹1為空時候
if(root2->c == 'f'){//如果當前樹2的值為f要加上值1024>>(level*2)
sum += 1024>>(level*2);//位運算的使用
return;//為f 說明子樹為空直接返回即可
}
for(int i = 0 ; i < 4 ; i++)//否則遍歷子樹2的四個方向
preorder(root1 , root2->child[i] , level+1);
return;//記得每一次都要返回
}
if(root2 == NULL){//同上
if(root1->c == 'f'){
sum += 1024>>(level*2);
return;
}
for(int i = 0 ; i < 4 ; i++)
preorder(root1->child[i] , root2 , level+1);
return;
}
//如果此時要個都不為空只要有一個是f就要加上對應值
if(root1->c == 'f' || root2->c == 'f'){
sum += 1024>>(level*2);
return;//返回上一層
}
for(int i = 0 ; i < 4 ; i++)//四個方向的遍歷
preorder(root1->child[i] , root2->child[i] , level+1);
} www.2cto.com
//輸入函數
void solve(){
pos = -1;
root1 = new Btree;
root2 = new Btree;
newnode(root1);//初始化
newnode(root2);
root1 = BuildTree(root1 , str1);//建樹
root2 = BuildTree(root2 , str2);//建樹
sum = 0;
preorder(root1 , root2 , 0);
printf("There are %d black pixels.\n" , sum);
}
//主函數
int main(){
int t;
scanf("%d" , &t);
while(t--){
scanf("%s%s" , str1 , str2);//輸入兩串字符串
solve();
}
return 0;
}
</span>
