【寒假坚持学习鸭】2.4（非二叉树递归建树）

题目链接：UVA-297
紫书p160
题意：用四分树来表示一个黑白图像：最大的图为根，然后按照图中的方式编号，从左到右对应4个子结点。如果某子结点对应的区域全黑或者全白，则直接用一个黑结点或者白结点表示；如果既有黑又有白，则用一个灰结点表示，并且为这个区域递归建树。
（以先序遍历输入）

思路：因为四分图比较特殊，只需给出先序遍历就可以确定整颗树。利用递归建树，遇见’p’就递归分别4个位置，每个位置记录左上角，再利用此次递归的边长得到方块的大小，边长每次缩小2倍。
当遇见’f’时从(r,c)到(r+w,c+w)累加没有加过位置的个数即为黑块大小。注意递归式中p也要引用，这样p++后才会改变p的值。

#include<cstdio>
#include<cstring>//32 × 32 units

const int len = 32;
const int maxn = 1024+10;
char s[maxn];
int buf[len][len],cnt;

void draw(const char* s, int& p, int r, int c, int w) {
   
	char ch = s[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
	}
	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++;}
	}
}

int main() {
   
	int T;
	scanf("%d", &T);
	while(T--) {
   
		memset(buf, 0, sizeof(buf));
		cnt = 0;
		for(int i = 0; i < 2; i++) {
   
			scanf("%s", s);
			int p = 0;
			draw(s, p, 0, 0, len);
		}
		printf("There are %d black pixels.\n", cnt);
	}
	return 0;
}