1 #include <iostream> 2 #define black 'f' 3 #define white 'e' 4 #define grey 'p' 5 using namespace std; 6 struct node{ 7 char type; 8 node* upper_r; 9 node* upper_l; 10 node* lower_l; 11 node* lower_r; 12 }; 13 node* build_tree(){ 14 node* root = new node; 15 cin >> root->type; 16 root->upper_l = root->upper_r = root->lower_l = root->lower_r = NULL; 17 if(root->type == grey){ 18 root->upper_r = build_tree(); 19 root->upper_l = build_tree(); 20 root->lower_l = build_tree(); 21 root->lower_r = build_tree(); 22 } 23 return root; 24 } 25 int fun(node* a,node* b,int p){ // p 为边长 , 表示当前处理的子方格边长 26 if(a->type == black || b->type == black){ // 有黑 27 return p * p; 28 }else if(a->type == white && b->type == white){ // 全白 29 return 0; 30 }else if(a->type == white){ // 白灰 31 return fun(b,b,p); 32 }else if(b->type == white){ // 灰白 33 return fun(a,a,p); 34 }else{ // 灰灰 35 int sum = 0; 36 sum += fun(a->upper_r,b->upper_r,p>>1); 37 sum += fun(a->upper_l,b->upper_l,p>>1); 38 sum += fun(a->lower_l,b->lower_l,p>>1); 39 sum += fun(a->lower_r,b->lower_r,p>>1); 40 return sum; 41 } 42 } 43 int main(){ 44 int t; 45 cin >> t; 46 while(t--){ 47 cin.get(); 48 node* a = build_tree(); 49 cin.get(); 50 node* b = build_tree(); 51 int ans = fun(a,b,32); 52 cout << "There are " << ans <<" black pixels." << endl; 53 } 54 return 0; 55 }
题目不难,考查递归的基本应用和细节。
另外,本题使用宏定义能够让代码逻辑更加清晰。