学步园

因为题目中已经告知四叉树深度不会超过5,那么它所拥有的最大结点数目为1365，所以我们可以使用四叉堆来保存它。

#include<stdio.h>
#include<string.h>

#define Max 1400
#define LIMIT 1365
#define LEAF_LEFT 342
#define LEAF_RIGHT 1365
#define ru(n) (((n)*4)-2)
#define lu(n) (((n)*4)-1)
#define ld(n) (((n)*4))
#define rd(n) (((n)*4)+1)

int ima[Max] = {0};

void dye(int i){
	int left = i,right = i,t;
	while( (t = ru(left)) <= LIMIT)left = t;
	while( (t = rd(right)) <= LIMIT)right = t;
	for( ; left <= right ; left ++){
		ima[left] = 1;
	}
}

void read(int i){
	char ch;
	scanf(" %c",&ch);
	if(ch == 'p'){
		read(ru(i));
		read(lu(i));
		read(ld(i));
		read(rd(i));
	}
	else if(ch == 'f'){
		dye(i);
	}
}

int proc_com(){
    int i,sum = 0;
	for(i = LEAF_LEFT ; i <= LEAF_RIGHT ; i ++)
	if(ima[i])sum ++;
    return sum;
}

int main(void){
	int n;
	scanf("%d",&n);
	while(n--){
		read(1);
		read(1);
        printf("There are %d black pixels.\n",proc_com());
		memset(ima,0,sizeof(ima));
	}
	return 0;
}