UVa 297 Quadtrees（树的递归）

Quadtrees

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

【题目类型】树的递归

&题意：
一个图片，像素是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.
",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;
}