题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=233
题目意思:
给两颗四叉树,每层有一个值,只要有一个为黑则为黑,否则为白,求两树的和。
解题思路:
用递归建树,用dfs求和。
代码:
#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<stack> #include<queue> #define eps 1e-6 #define INF (1<<20) #define PI acos(-1.0) typedef struct Node node; using namespace std; struct Node { int black; node * son[4]; //四个孩子的节点指针 }; char string1[2000],string2[2000]; char *p; int sum; node * build() { node * temproot=(node *)malloc(sizeof(node)); if(*p=='p') { temproot->black=0; for(int i=0;i<4;i++) //一定有四个孩子 { p++; temproot->son[i]=build(); } } else { if(*p=='f') temproot->black=1; else temproot->black=0; for(int i=0;i<4;i++) //分别为叶子节点 temproot->son[i]=NULL; // p++; //注意p不用加 } return temproot; } void dfs(node * root1,node *root2,int height) { if(root1==NULL&&root2==NULL) //两棵树都加完了 return ; if(root1==NULL) //如果第一棵树此节点为叶子节点,则按第二棵树的情况来处理 { if(root2->black) { sum+=(1024>>(height*2)); //每个一层除以4 return ; } else { for(int i=0;i<4;i++) //将此以此节点为根的子树全部算完 dfs(root1,root2->son[i],height+1); return ; } } if(root2==NULL) //如果第二棵树此节点为叶子节点,则按第一棵树的情况来处理 { if(root1->black) { sum+=(1024>>(2*height)); return ; } else { for(int i=0;i<4;i++) dfs(root1->son[i],root2,height+1); return; } } if(root1->black||root2->black) //如果有一个为黑,则后面的统统不用算 { sum+=(1024>>(height*2)); return ; } for(int i=0;i<4;i++) //两个都是白色的,继续 dfs(root1->son[i],root2->son[i],height+1); return ; } int main() { int ca; scanf("%d",&ca); while(ca--) { scanf("%s%s",string1,string2); p=string1; //用两个指针来访问,统一,简便 node * tree1=build(); p=string2; node * tree2=build(); sum=0; int height=0; dfs(tree1,tree2,height); //用两个根来访问两棵树 printf("There are %d black ",sum); sum==1?printf("pixel.\n"):printf("pixels.\n"); } return 0; }