算法刷题——四分树(Uva 297)

  |   0 评论   |   0 浏览

1.题目描述

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

15783879881.png
若图像的大小为 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],可得:
T_c[i] = max(T_1[i],T_2[i])
  1. 最后统计的过程可以看做由根节点开始DFS,
  • 若节点为黑色,最终结果加上(1024 / 该节点所在层数)。
  • 若节点为灰色,继续向下搜索。
  • 若节点为白色,对结果没有影响不做处理。
  1. 算法输入采用递归的形式,若当前节点为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;
}



标题:算法刷题——四分树(Uva 297)
作者:YaoCheng8667
地址:https://ycisme.xyz/articles/2020/01/07/1578389878887.html