yc 的个人博客

1.题目描述

可以使用一个四分树表示一个黑白图像，方法是使用根节点表示整幅图像，然后把行列各分成两等分，按照图中方式编号，从左到右对应四个子节点。如果某子节点对应的区域为全黑或全白，则直接用一个黑节点或白节点表示；如果既有黑又有白，则用一个灰节点表示，并且为这个地方递归建树。

若图像的大小为 1024\times1024 ， 给出两棵四分树的先序遍历，求两者合并后的黑色像素的个数。p表示中间节点，f表示黑色(full)，e表示白色(empty)。
输入格式为先输入组数n，接下来$2n$行，每两行代表相加的两棵树，输出格式见样例输出。

样例输入

3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe

样例输出

There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.

2. 问题分析

1. 书中的解法为使用一个二维数组模拟图像，根据树的定义将其画出来。
2. 我的思路是既然图的大小已经固定，可以按照类似完全二叉树的建树方法，采用数组存放整个二叉树，数组大小 maxn 为 1+4+16+64+256+1024 ，编号按照完全二叉树的方法从上至下从1开始分层编号。
   编号后对于任意节点若其编号为i，其4个子节点为 4i-2,4i-1,4i 以及 4i+1 。
3. 按照2中方法建立二叉树后，对于每个节点，用2表示黑色，1表示灰色，0表示白色。将二叉树合并的过程实则为合并两个存储二叉树的数组。
   设数组为T_1[maxn]，T_2[maxn]，合并后为T_c[maxn]，可得：

4. 最后统计的过程可以看做由根节点开始DFS，

• 若节点为黑色，最终结果加上(1024 / 该节点所在层数）。
• 若节点为灰色，继续向下搜索。
• 若节点为白色，对结果没有影响不做处理。

5. 算法输入采用递归的形式，若当前节点为p，接下来的输入为以其四个孩子为根节点的子树。

Tips

1. 不可采用遍历整个数组的方式，因为黑色节点的子树上可能还有黑色节点，会重复计算。
2. 时间复杂度为O(n+m)，n和m为合并两棵树的节点数，优于书中直接画图的方法，但空间上占得更多。

3. Mycode

#include <iostream>
#include <cstring>
/**
Date: 2020/1/5
Author: YC
*/

using namespace std;
const int maxn = 1+4+16+64+256+1024;
int t1[maxn+1];
int t2[maxn+1];
int cs;
char tc;
int re;

void read_t(int root,int* t){
    cin >> tc;
    //cout<<"r"<<root<<endl;
    switch(tc){
        case 'e': break;
        case 'f':
            t[root] = 2;break;
        case 'p':
            t[root] = 1;
            read_t(root*4-2,t);
            read_t(root*4-1,t);
            read_t(root*4,t);
            read_t(root*4+1,t);
            break;
    }
}

void cal(int root,int val){
    if(t1[root] == 2) re+= val;
    if(t1[root] == 1) {
        cal(root*4 - 2,val/4);
        cal(root*4 - 1,val/4);
        cal(root*4, val/4 );
        cal(root*4 + 1,val/4);
    }
}
inline void Do(){
    cin>>cs;
    int ind;
    while(cs--){
        memset(t1,0,sizeof(t1));
        memset(t2,0,sizeof(t2));
        re = 0;
        ind = 1;
        read_t(1,t1);
        read_t(1,t2);
        for(ind = 0;ind < maxn;ind++)
            t1[ind] = (t1[ind] > t2[ind] ? t1[ind] : t2[ind]);
        cal(1,1024);
        cout<<"There are "<<re<<" black pixels."<<endl;
    }
}

int main()
{
    Do();
    return 0;
}