This is the personal work of Denis Dmitriev; it is not an officially verified or endorsed solution.
Denis writes: This solution is extremely straightforward -- we're just reading both trees' specifications, building these trees on the same grid, and counting the number of covered pixels in the result. -DD
#include <stdio.h> #include <stdlib.h> #include <string.h> struct rect { int x,y,w,h; }; /* this is the main processing function. it's job is to read * the tree specification and to fill the grid respectively */ void fill_tree(char tree[32][32],rect r,FILE *fp) { int c,i,j; rect sr; c=fgetc(fp); switch(c) { case 'e': /* empty parts are just skipped * (grid is cleared beforehand) */ return; case 'f': /* fill the cell */ for(i=r.x;i<r.x+r.w;i++) for(j=r.y;j<r.y+r.h;j++) tree[i][j]=1; return; case 'p': /* our cell (bounded by `r') is a parent. set up * the rectangles for sub-cells and call `fill_tree' * recursively for them */ sr.w=r.w/2,sr.h=r.h/2; sr.x=r.x+r.w/2,sr.y=r.y; fill_tree(tree,sr,fp); sr.x=r.x,sr.y=r.y; fill_tree(tree,sr,fp); sr.x=r.x,sr.y=r.y+r.h/2; fill_tree(tree,sr,fp); sr.x=r.x+r.w/2,sr.y=r.y+r.h/2; fill_tree(tree,sr,fp); return; } } void main(void) { FILE *fp=fopen("quad.in","r"); FILE *fo=fopen("quad.out","w"); rect r; r.x=r.y=0; r.w=r.h=32; char tree[32][32]; char buf[256]; int i,j,cnt,tests; fgets(buf,256,fp); tests=atoi(buf); for(;tests--;) { /* clear the grid */ memset(tree,0,sizeof(tree)); fill_tree(tree,r,fp); /* skip the rest of line */ fgets(buf,256,fp); fill_tree(tree,r,fp); /* skip the rest of line */ fgets(buf,256,fp); /* count the number of covered pixels */ for(cnt=i=0;i<32;i++) for(j=0;j<32;j++) if(tree[i][j]) cnt++; /* print the answer */ fprintf(fo,"There are %d black pixels.\n",cnt); } fclose(fo); fclose(fp); }