UVA.297 Quadtrees (四分树 DFS)

题意分析

将一个正方形像素分成4个小的正方形，接着根据字符序列来判断是否继续分成小的正方形表示像素块。字符表示规则是：

p表示这个像素块继续分解，e表示当前方格没有像素，即为空，f表示当前像素块为满，黑色。

最后求解两个数合并后的像素块的数量是多少。

最大的像素块数量是1024个。

采用数组模拟，根据所给的字符串，递归建树。字符数组的建四分树的技巧是(k << 2) + i i∈[-2,1]。 这样就可以充分利用数组的空间。

两树合并的技巧，对于某一节点，如果有一个节点的值为0，另一个对应节点的值为非0，那么这个节点合并后的值就为非0值。 或者是当前节点的像素块为此深度所能到达的最大值，那么合并后即为这个深度的最大值。否则的话，继续向下递归合并。

最后输出合并后的结果即可。

代码总览

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <string>

#include <sstream>

#include <queue>

#include <stack>

#include <set>

#include <map>

#include <vector>

#define nmax 1200

#define standerd 1024

#define hh standerd / (1<<((depth-1)*2))

#define INF 0x3f3f3f3f

using namespace std;

int ta[nmax<<2],tb[nmax<<2];

char str[10000];

int pos = 0;

void pushup(int rt, int t[])

{

    int sum = 0;

    for(int i = -2; i<=1; ++i)

        sum+=t[(rt<<2)+i];

    t[rt] = sum;

}

void dfs(int t[],int rt,int depth)

{

    if(str[pos] == 'e') {

        return;

    }

    if(str[pos] == 'f') {

        t[rt] = hh;

    }

    if(str[pos] == 'p'){

        for(int i = -2; i<=1; ++i){

            pos++;

            dfs(t,(rt<<2)+i,depth+1);

            pushup(rt,t);

        }

    }

}

bool judge(int depth, int rt)

{

    if(ta[rt] == hh || tb[rt] == hh) return true;

    else return false;

}

int cal(int t1[], int t2[],int rt,int depth, int sum)

{

    if((!t1[rt] || !t2[rt])|| judge(depth,rt))

        sum = max(t1[rt],t2[rt]);

    else

        for(int i = -2; i<=1; ++i)

            sum += cal(t1,t2,(rt<<2)+i,depth+1,0);

    return sum;

}

int main()

{

//    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

    int t;

    scanf("%d",&t);

    while(t--){

        memset(ta,0,sizeof(ta));

        memset(tb,0,sizeof(tb));

        pos = 0;

        scanf("%s",str);

        dfs(ta,1,1);

        pos = 0;

        scanf("%s",str);

        dfs(tb,1,1);

        int sum = cal(ta,tb,1,1,0);

        printf("There are %d black pixels.\n",sum);

    }

    return 0;

}