首页 > 代码库 > 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 四分树