# Quadtrees

四分树就是一颗一个结点只有4个儿子或者没有儿子的树

【题目链接】UVa 297 Quadtrees

【题目类型】树的递归

&题意：
一个图片，像素是32*32，给你两个先序递归的字符串，要你把他俩合起来输出面积。p代表结点，f代表黑色，e代表白色。

&题解：
用字符串来模拟buf32*32的数组，递归模拟出模型，黑色的涂成1，白色的不处理（也就是0），最后输出1的个数就好了

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(ll i=0;i<(b);i++)

const int len=32;

const int maxn=1024+5;

char s[maxn];

int buf[len][len],cnt;

//s是输入的串，p是处理到第几个了，r和c是处理区域的左上角坐标，w是边长（因为处理区域是正方形，所以r c w就可以确定区域了）

void draw(const char* s,int& p,int r,int c,int w){

	char ch=s[p++];

        //是p继续递归

	if (ch=='p'){

		draw(s,p,r,c+w/2,w/2); //1

		draw(s,p,r,c,w/2); //2

		draw(s,p,r+w/2,c,w/2); //3

		draw(s,p,r+w/2,c+w/2,w/2); //4

	}

        //黑色就把这个区域给涂成1

	else if (ch=='f'){

		for(int i=r;i<r+w;i++)

			for(int j=c;j<c+w;j++)

				if (buf[i][j]==0) buf[i][j]=1,cnt++;

	}

}

void Solve()

{

	cle(buf,0);

	cnt=0;

	rep(i,2){

		scanf("%s",s);

		int p=0;

		draw(s,p,0,0,len);

	}

	printf("There are %d black pixels.\n",cnt);

}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("in.txt", "r", stdin);

//	freopen("out.txt","w",stdout);

#endif

	int T;cin>>T;while(T--)

	Solve();

	return 0;

}