题目链接:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=389#problem/C

坑爹的题,开始没有一点思路,别人的代码好诡异,看不懂,木办法自己想了一天才搞出来!

思路:用第一组数据建树,用第二组数据在已经建立好的树上进行修改,修改完后再遍历树,求像素!

#include <stdio.h>
#include <string.h>
#include <malloc.h>
int sum;
char *s;
typedef struct node
{
char word;
int depth;
struct node *next1,*next2,*next3,*next4;
}node;
char str1[1400],str2[1400];
node *b_tree(int n)//建树
{
node *p;

p=(node *)malloc(sizeof(node));
p->word=*s;
p->depth=n+1;
s++;
if(p->word==’p’)
{
p->next1=b_tree(p->depth);
p->next2=b_tree(p->depth);
p->next3=b_tree(p->depth);
p->next4=b_tree(p->depth);
}
else if(p->word==’f’||p->word==’e’)
{
p->next1=NULL;
p->next2=NULL;
p->next3=NULL;
p->next4=NULL;
}
return p;
}
void plus(node *p)//修改树
{
if(p->word==’f’||*s==’f’)
{
s++;
p->word=’f’;
p->next1=NULL;
p->next2=NULL;
p->next3=NULL;
p->next4=NULL;
return ;
}
else if(p->word==’e’&&*s==’p’)
{
s++;
p->word=’p’;
p->next1=b_tree(p->depth);
p->next2=b_tree(p->depth);
p->next3=b_tree(p->depth);
p->next4=b_tree(p->depth);
}
else if(p->word==’e’&&*s==’e’)
{
s++;
return ;
}
else if(p->word==’p’&&*s==’e’)
{
s++;
return ;
}
else if(p->word==’p’&&*s==’p’)
{
s++;
plus(p->next1);
plus(p->next2);
plus(p->next3);
plus(p->next4);
return ;
}
}
int number(int n)
{
int sum=1,i;
if(n==1)
return sum;
else
{
for(i=1;i<n;i++)
sum*=4;
}
return sum;
}
void sump(node *p)//遍历求像素
{
if(p->word==’f’)
{
sum+=32*32/number(p->depth);
}
else if(p->word==’p’)
{
sump(p->next1);
sump(p->next2);
sump(p->next3);
sump(p->next4);
}
}
int main()
{
int T,i;
node *head;
scanf(“%d”,&T);
getchar();
for(i=0;i<T;i++)
{
sum=0;
gets(str1);
s=str1;
head=b_tree(0);
gets(str2);
s=str2;
plus(head);
sump(head);
printf(“There are %d black pixels.\n”,sum);
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation