uva 297 Quudtrees（線分樹思想、区間操作）
5471 ワード
線分数区間の操作の思想を参考にして、ただ一つの結点の子供を四つに広げました。
結点k、4人の子供の番号はそれぞれ4*k+1、4*k+2、4*k+3、4*K+4で、ゼロから始まります。
レイヤー数に基づいて、権利値を決定します。
結点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;
}