题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=233
题目类型: 数据结构, 二叉树
题意与背景:
同二叉树一样,四叉树也是一种数据结构,是一种每个节点最多有四个子树的数据结构。
一个四叉树是可以表示格式用于编码图像。背后的基本思想是, 任何图像可以分为四个象限,每个象限也可以再次被分割成4个亚象限,等等。因此四叉树是在二维图片中定位像素的唯一适合的算法。
当然, 如果一整幅图只有一种一种颜色,那么可以只用一个单一的节点表示。一般来说, 如果图片的像素的不同颜色组成,那么每个象限只需要再被细分下去。因此,四叉树不需要统一的深度。
现代计算机艺术家在黑白图像32*32单元下工作, 每幅图像总计有1024像素。其中一个需要执行的操作是添加两个图像,把它们合并形成一个新形象。两幅图像合并,在相对应的象限的像素中,只要一副中是黑色的,那么合并后该像素就是黑色的,否则就是白色的。
例如:
样例输入:
3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe
样例输出:
There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.
分析:
题目就是分别给出关于两幅图在四叉树数据结构中的表示的按照前序遍历得到的序列, 然后要求我们求出合并后的图像的黑色像素有多少个。
其中,p代表是一个父节点(parent),f表示表示该节点是黑色的(full), e 表示该节点是白色的(empty).
我的方法是,首先, 需要按照所给的序列构造出两幅图的四叉树,可以通过递归的方法进行构造,和构造二叉树十分像。
然后,就是对两棵树进行计算的过程。具体是下面的代码
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str1[100005], str2[100005];
class Node{
public:
char data;
Node *son[4];
};
Node node[20000];
int nIndex, pos1,pos2, sum;
inline Node* NewNode(){
node[nIndex].data = 0;
for(int i=0; i<4; ++i) node[nIndex].son[i] = NULL;
return &node[nIndex++];
}
// 通过序列建树
Node *BuildTree(Node* root, int &pos, char *str){
++pos;
if( pos==strlen(str) ) return NULL;
root = NewNode();
root->data=str[pos];
if(str[pos]=='p') {
for(int i=0; i<4; ++i){
if(root->son[i]==NULL){
root->son[i] = BuildTree(root->son[i], pos, str);
}
}
}
return root;
}
// 用深搜遍历两棵树求出合并后的黑色像素个数
void dfs(Node *root1, Node *root2, int level){
if(!root1 && !root2) return ;
if(!root1){
if(root2->data=='f'){
sum += 1024>>(level*2);
return;
}
for(int i=0; i<4; ++i)
dfs(root1, root2->son[i], level+1);
return;
}
if(!root2){
if(root1->data=='f'){
sum += 1024>>(level*2);
return;
}
for(int i=0; i<4; ++i)
dfs(root1->son[i],root2, level+1);
return;
}
if(root1->data=='f' || root2->data=='f'){
sum += 1024>>(level*2);
return ;
}
for(int i=0; i<4; ++i)
dfs(root1->son[i], root2->son[i], level+1);
}
void output(Node *root){
if(root){
printf("%c",root->data);
for(int i=0; i<4; ++i)
output(root->son[i]);
}
}
void Solve(){
Node *root1=NULL, *root2=NULL;
pos1=-1, pos2=-1;
nIndex=0;
root1 = BuildTree(root1,pos1, str1);
root2 = BuildTree(root2,pos2, str2);
sum = 0;
dfs(root1, root2 ,0);
printf("There are %d black pixels.\n", sum);
}
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int T;
scanf("%d%*c",&T);
while(T--){
scanf("%s %s", str1,str2);
Solve();
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
正弦信号的matlab代码使用DCT和四叉树进行图像压缩 简介图像压缩:图像压缩可最大程度地减小图形文件的字节大小,而不会降低图像质量到不可接受的水平。 文件大小的减小允许在给定数量的磁盘或内存空间中存储更多...
quadtree-js, 另一个用于javascript的四叉树实现 四叉树 js这是本教程中介绍的Java方法的JavaScript四叉树实现: http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-
BentoMap是四叉树quadtrees的实现,用于地图标注集群和存储采用Swift开发。
四叉树 如何使用您可以下载quadtree.js并将其包含在您的p5草图中,或通过以下CDN链接进行引用: < script src =" https://cdn.jsdelivr.net/gh/CodingTrain/QuadTree/quadtree.js " > </ script > 一旦...
Continuous LOD terrain meshing using adaptive quadtrees 770 2D surface deformation 782 Lone game developper battles physics simulator 795 Collision response : bouncy, trouncy, fun 801 Simultaneous ...
生活质量简介/恢复该库实现了Quadtrees和Octrees(以Point和Region两种形式)的简单版本,该库是出于教育目的而创建的,请不要尝试在生产系统中使用它。 可以轻松实现四方树和八叉树形式的简易图书馆(点对点地区的...
4.30 Quadtrees 461 4.31 Quadrisection 478 4.32 Space-Filling Curves 485 4.33 Hilbert Scan and VQ 487 4.34 Finite Automata Methods 497 4.35 Iterated Function Systems 513 4.36 Cell Encoding 529 xxiv ...
QuadTrees空间细分 广相碰撞检测 分离轴定理 窄相碰撞检测 瓷砖引擎 精灵系统 渲染动画图像和纯色。 附加功能 Emscript6模块减小包装尺寸 附加模块 资产模块 加载图像,音频和json文件。 输入模块 捕获键盘输入 ...
You'll dive deep into how scripting engines encode behavior, how quadtrees and other spatial partitions optimize your engine, and how other classic design patterns can be used in games. Table of ...