Uva297 Quadtrees

题意：用四分树来表示一个黑白图像：最大的图为根，然后按照图中的方式编号，从左到右对应4个子结点。如果某子结点对应的区域全黑或者全白，则直接用一个黑结点或者白结点表示；如果既有黑又有白，则用一个灰结点表示，并且为这个区域递归建树。

分析：比较新颖的一道题因为最多有1024个节点嘛，我们利用这个四分树把整个图给建出来，建图的过程中动态统计答案就可以了，利用递归来建图，每次都找准左上角，只有当前节点是灰色才往下递归，否则是黑色的话直接覆盖就可以了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int len = 32, maxn = 10010;
int T,ans,a[len][len];
char ch[maxn];

void dfs(int &cur, int x, int y, int w)
{
    char c = ch[cur++];
    if (c == 'p')
    {
        dfs(cur, x, y + w / 2, w / 2);
        dfs(cur, x, y, w / 2);
        dfs(cur, x + w / 2, y, w / 2);
        dfs(cur, x + w / 2, y + w / 2, w / 2);
    }
    else
        if (c == 'f')
        {
        for (int i = x; i < x + w; i++)
            for (int j = y; j < y + w; j++)
                if (a[i][j] == 0)
                {
                    a[i][j] = 1;
                    ans++;
                }
        }
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        ans = 0;
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= 2; i++)
        {
            scanf("%s", ch);
            int p = 0;
            dfs(p, 0, 0, len);
        }
        printf("There are %d black pixels.
", ans);
    }

    return 0;
}