首页 > 代码库 > Quadtrees UVA 297

Quadtrees UVA 297

2024-07-22 08:08:08   223人阅读

说说：

先来说说题意，题目给定了一个32*32大小（相当于1024个1*1的小正方形合成）的正方形，如下图所示：

其实每个大正方形可以看成一个树根，它由四个小正方形组成，四个小正方形为孩子。当然，我们可以立即给小正方形上色，黑色或白色，还可以把小正方形再细分成更小的四个正方形，直至正方形的大小为1*1为止。现在题目给你两个字符串，例如：

ppeeefpffeefe
pefepeefe
其中p表示该节点不是叶子节点，e表示为白色的叶子节点，f为黑色的叶子节点。整个字符串是先序遍历的结果。要求求出两个这样的正方形叠加，最后形成的正方形中1*1的黑色小方格的数目。开始我的做法是，分别遍历两棵树，求出每棵树黑色小正方形的数目，然后将两个值叠加。但后来发现不对，因为两个正方形有重叠的部分。因此只能构建一个数组，代表1024个小正方形。然后再遍历两棵树，当遇到黑色叶子节点时，将相应区间内的数组置位即可。


源代码：

#include <stdio.h>
#include <string.h>

char ans[1024];//1024个最小的方格
void search(int,int);

int main(){
  int N,result,i;
  char c;

//  freopen("data","r",stdin);
  scanf("%d",&N);
  while((c=getchar())!='\n');
  while(N--){
    memset(ans,0,sizeof(ans));
    search(0,1024);
    getchar();
    search(0,1024);
    getchar();
    result=0;
    for(i=0;i<1024;i++)
     if(ans[i]==1)
       result++;
     printf("There are %d black pixels.\n",result);
  }

  return 0;
}

void search(int begin,int end){//begin和end为当前节点覆盖的小方格的区间
   char c;
   int i,j,add=(end-begin)/4;
   
   c=getchar();
   if(c=='f'){//黑色叶子节点
     for(j=begin;j<end;j++)
       ans[j]=1;
     return;
   }
   else if(c=='p'){//非叶子节点则要遍历四棵子树
     for(i=0;i<4;i++){
       if((c=getchar())=='f'){//若子树即为叶子节点,直接操作
          for(j=begin;j<begin+add;j++)
	    ans[j]=1;
       }
       else if(c=='p'){
          ungetc(c,stdin);
          search(begin,begin+add);
       }
       begin+=add;
     }
   }

  return;
}



Quadtrees UVA 297


联系
我们