题目： 如图6-8所示，可以用四分树来表示一个黑白图像，方法是用根结点表示整幅图像，然后把行列个分城两等分，按照图中的方式编号，从左到右对应4个子结点。如果某子结点对应的取余全白或全黑，则直接用一个黑结点或者白结点表示：如果即有黑又有白，则用一个灰结点表示，并且为这个区域递归建树。
给出两棵四分树的先序遍历，求二者合并之后（黑色部分合并）黑色像素的个数。p表示中间结点，f表示黑色（full），e表示白色（empty）。
每个图的大小都为32*32，输出黑色块的个数。
文章图片
分析与解答： 1.输入字符串，然后调用函数
2.函数中，遇见p就模拟建树，这个题用到了利用坐标的技巧来分割区域，
行 Row
列 Column
文章图片
【（DFS）四分树】3.注意你遍历涂色时候，是根据黑色坐标的范围来对大矩阵赋值的，所以他每次调用传递坐标，传递w。
#include
#includeconst int len = 32;
const int maxn = 1024 + 10;
char s[maxn];
int buf[len][len], cnt;
// 把字符串s[p..]导出到以(r,c)为左上角，边长为w的缓冲区中
// 2 1
// 3 4
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;
}
