UVA_297

    由于这个题目可以看成是完全四叉树，所以借用了一下线段树的思想，把题目转化成了对区间进行两次染色，然后求最后色块的个数。

    当然我的程序写得复杂了，lazy可以不用的，在统计的时候遇到黑色节点就返回即可，只不过这样计数的方式就要稍加变化了。

#include
     
       #include
      
        #define MAXD 4000 int tree[MAXD], lazy[MAXD], cur, M, res; char b[1500]; void down(int t) {
   if(lazy[t] == 1)     {
           tree[t] = 1, lazy[t] = 0; if(t < M)             lazy[4 * t - 2] = lazy[4 * t - 1] = lazy[4 * t] = lazy[4 * t + 1] = 1;     } } void build(int t) {
   int i;     down(t); if(b[cur] == 'f')     {
           lazy[t] = 1;         cur ++;     } else if(b[cur] == 'e')         cur ++; else     {
           cur ++; for(i = -2 ; i <= 1; i ++)             build(4 * t + i);     } } void dfs(int t) {
   int i;     down(t); if(t >= M)     {
   if(tree[t])             res ++;     } else     {
   for(i = -2; i <= 1; i ++)             dfs(4 * t + i);     } } void solve() {
   int i, j; for(i = 1, M = 1; i <= 5; i ++, M = (M << 2) - 2);     memset(tree, 0, sizeof(tree));     memset(lazy, 0, sizeof(lazy));     gets(b);     cur = 0;     build(1);     gets(b);     cur = 0;     build(1);     res = 0;     dfs(1);     printf("There are %d black pixels.\n", res); } int main() {
   int t;     gets(b);     sscanf(b, "%d", &t); while(t --)     {
           solve();     } return 0; }