Denis' Solution 1C: Quadtrees

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

C++ Source Code

#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);
}