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; }