297 - Quadtrees*****
2519 ワード
/*
。。。。
, 。*****
:
*
*
*
, ,
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
using namespace std;
struct Node
{
char ch;
Node *fir,*sec,*thi,*fou;
};
string a;
int sum;
Node *creat(int &loc)
{
/*
:
1:
2:
*/
Node *r=(Node *)malloc(sizeof(Node));
if(loc<a.size())
{
r->ch=a[loc];
if(a[loc]=='p')
{
r->fir=creat(++loc);
r->sec=creat(++loc);
r->thi=creat(++loc);
r->fou=creat(++loc);
}
else
r->fir=r->sec=r->thi=r->fou=NULL;
}
return r;
}
Node *combine(Node *root1,Node *root2)
{
Node *r=(Node *)malloc(sizeof(Node));
if(root1->ch=='f' || root2->ch=='f')
{
r->ch='f';
r->fir=r->sec=r->thi=r->fou=NULL;
}
else if(root1->ch=='e' && root2->ch=='e')
{
r->ch='e';
r->fir=r->sec=r->thi=r->fou=NULL;
}
else
{
r->ch='p';
if(root1->ch=='p' && root2->ch=='p')
{
r->fir=combine(root1->fir,root2->fir);
r->sec=combine(root1->sec,root2->sec);
r->thi=combine(root1->thi,root2->thi);
r->fou=combine(root1->fou,root2->fou);
}
else if(root1->ch=='p' && root2->ch=='e')
{
r->fir=root1->fir;
r->sec=root1->sec;
r->thi=root1->thi;
r->fou=root1->fou;
}
else
{
r->fir=root2->fir;
r->sec=root2->sec;
r->thi=root2->thi;
r->fou=root2->fou;
}
}
return r;
}
void cacluate(Node *root,int len)
{
/*
if(root->ch=='p')
{
len=len/4;
cacluate(root->fir,len);
cacluate(root->sec,len);
cacluate(root->thi,len);
cacluate(root->fou,len);
}
else if(root->ch=='f')
sum+=len;
*/
if(root!=NULL)
{
if(root->ch=='f')
sum+=len;
len=len/4;
cacluate(root->fir,len);
cacluate(root->sec,len);
cacluate(root->thi,len);
cacluate(root->fou,len);
}
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int T;
cin>>T;
while(T--)
{
int loc;
loc=0;
cin>>a;
Node *root1=creat(loc);
cin>>a;
loc=0;
Node *root2=creat(loc);
Node *root=combine(root1,root2);
sum=0;
cacluate(root,1024);
printf("There are %d black pixels.
",sum);
}
return 0;
}