uva297 Quadtrees (线段树思想，区间操作)

借鉴了线段数区间操作的思想，只是把一个结点的孩子扩展到了4个，

结点k，四个孩子编号分别为4*k+1，4*k+2，4*k+3,4*K+4,从零开始。

根据层数，确定权值。

#include<cstdio>
#include<cstring>

const int maxn = 1365 + 5;//4^5 + 4^4 + ... + 1

char s[maxn];

int tr[maxn];

int p;
void add(int o)
{
   char ch = s[p++];//
   if(ch == 'p'&&!tr[o]) {
      int no = o<<2;
      for(int i = 1; i <=4; i++)
         add(no+i);
   }
   else if(ch == 'f') {
      tr[o] = 1;
   }
}

int w[] = {1024,256,64,16,4};
int query(int o,int l)
{
   if(l == 5) return tr[o];
   int ans = 0;
   if(!tr[o]){
      int no = o<<2; l++;
      for(int i = 1; i <=4; i++) {
         ans += query(no+i,l);
      }
   }
   else {
      ans += w[l];
   }
   return ans;
}

int main()
{
 //  freopen("in.txt","r",stdin);
   int T;
   scanf("%d",&T);
   while(T--) {
      memset(tr,0,sizeof(tr));
      for(int i = 0; i < 2; i++){
         scanf("%s",s);
         p = 0;
         add(0);
      }
      printf("There are %d black pixels.
",query(0,0));
   }
　　return 0;
}