UVA 297Quadtrees（四分图）

UVA 297

题意

有一副32 X 32像素的图像，用四分图来表示，先序输入两个四分图，合并后统计黑色像素的个数，（p表示中间节点，f表示黑像素，e表示白像素）

四分图表示图像，用根节点表示整幅图，然后把图像化为4部分，按图中顺序递归建树。

例：

Sample Input
3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe
Sample Output
There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.

分析

• 首先四分图根据先序就可以确定整个树，因为它有中间节点，一个节点要么有四个儿子，要么没有儿子。
• 分两次将两个四分图画出来，边画边统计黑色像素即可
• $buf$buf数组表示整幅图，重点时递归四个儿子时，参数的变化

#include<bits/stdc++.h>
using namespace std;
const int N = 1024 + 10;
const int INF = 0x3f3f3f3f;

int _, len = 32;
char s[N];
int buf[N][N], 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);    
        draw(s, p, r, c, w / 2);
        draw(s, p, r + w / 2, c, w / 2);
        draw(s, p, r + w / 2, c + w / 2, w / 2);
    }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()
{
    for (scanf("%d", &_); _;_--){
        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;
}