uva 297 Quudtrees（線分樹思想、区間操作）

線分数区間の操作の思想を参考にして、ただ一つの結点の子供を四つに広げました。
結点k、4人の子供の番号はそれぞれ4*k+1、4*k+2、4*k+3、4*K+4で、ゼロから始まります。
レイヤー数に基づいて、権利値を決定します。
 

/*jerryRey

       ，  

http://www.cnblogs.com/jerryRey/

*/

#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;

}