学步园

UVA_297

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

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

#include<stdio.h>
#include<string.h>
#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;
}