6_11 四分树(UVa297)<四分树>

一幅图有1024个点, 可以对图平均分成4块, 并且子图也可以再往下分, 直到一个子图表示一个点。 f表示这块子图填满, p表示它还有4个子图, e表示没有子图(当然啦, 它也没有填满)。 给定两个字符串(其实就是两幅图, 两棵树), 求把两图合并后的图的黑点数。

Example Input:
3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe


Example Output:
There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.

[分析]

搜索、数据结构。把图片分成1024块1*1的小正方形,建立一位数组记录对应小正方形的颜色。

利用递归根据字符串,建立相应四叉树。在建树的过程中,树节点计算当前节点对应的小正方形

编号区间。这里处理类似于线段树,将父节点的区间等分成4份分别对应四棵子树的编号区间。

建树到达叶子时(color为‘f’或者‘e’),直接将颜色数组赋值即可。当树建完时,颜色数组即染色

完毕。将两棵树依次染色到同一数组,统计黑色节点个数即可。

原文地址:https://www.cnblogs.com/jjzzx/p/5542515.html