首页 > 代码库 > UVa 297 四分树
UVa 297 四分树
题意:每张图片可分为1024个像素,用四叉树结构表示。最高高度5。每个像素或黑或白,即或1或0.现将两个这样的图,即树合并,同一位置的像素其中一张是黑,则结果是黑色。求最终合并的图中有多少黑像素。
思路:最直接的思路就是构建四叉树,然后对两个四叉树进行合并对比吧。把四叉树建好之后,发现不会合并了,想了下,很复杂。网搜的有对比四叉树以及填充数组这两种思路。其中有一个直接没有建树、填数组就行了,没仔细看。最终我在四叉树建好之后,让叶子结点或者说 f 结点来填数组,两棵树各填一次,最终统计1的个数。
建树的时候是利用栈,只将 p 结点入栈,给栈顶元素赋满四个孩子后出栈。 后面处理是用深搜,递归实现。只不过在遇到 f 结点时进行填数组。
建树方面还是比较顺利的,就是后面处理纠结了很长时间,察觉到“对每个结点填数组可以递归地设定填的起始位置和宽度”后还是很容易写的。没什么小错误,就是最后输出的地方输出的是句子不是单个数字,WA了一次。。 要学会用递归
Code:
#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXN 100 typedef struct qnode { int data; struct qnode *y,*e,*sa,*si; }Qnode; void count(); void dfs(Qnode *r,int fw,int st); void fill(int st,int fw); Qnode* build(); Qnode* newnode(); void remove_tree(Qnode *root); int pix[1024]; int main() { int n=0; scanf("%d",&n); getchar(); while(n-->0) { Qnode* root1=build(); Qnode* root2=build(); memset(pix,0,sizeof(pix)); dfs(root1,1024,0); dfs(root2,1024,0); count(); remove_tree(root1); remove_tree(root2); } return 0; } void count() { int cnt=0; for(int i=0;i<1024;++i) if(pix[i]) cnt++; printf("There are %d black pixels.\n",cnt); } void dfs(Qnode *r,int fw,int st) {//st为数组应填的起始下标,fw为要填充的宽度或范围。 if(r==NULL) return ; if(r->data=http://www.mamicode.com/=1) fill(st,fw);>UVa 297 四分树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。