UVa 297 - Quadtrees

题目：利用四叉树处理图片，给你两张黑白图片的四叉树，问两张图片叠加后黑色的面积。

分析：搜索、数据结构。把图片分成1024块1*1的小正方形，建立一位数组记录对应小正方形的颜色。

利用递归根据字符串，建立相应四叉树。在建树的过程中，树节点计算当前节点对应的小正方形

编号区间。这里处理类似于线段树，将父节点的区间等分成4份分别对应四棵子树的编号区间。

建树到达叶子时（color为‘f’或者‘e’），直接将颜色数组赋值即可。当树建完时，颜色数组即染色

完毕。将两棵树依次染色到同一数组，统计黑色节点个数即可。

注意：数组大小，防止RE。

#include <iostream>  
#include <cstdlib>  
#include <cstring>  
#include <cstdio>  
#include <cmath>  
  
using namespace std;  
  
int Color[1024];  
  
typedef struct tnode  
{  
    char   color;  
    tnode* child[4];  
}tnode;  
tnode *root;  
tnode  Node[1365];  
int    Count;  
  
tnode* dfs( char* word, int &move, int a, int b )  
{  
    tnode* root = &Node[Count ++];  
    root->color = word[move ++];  
    if ( root->color == 'p' ) {  
        int mid = (a+b)>>1;  
        int m_l = (a+mid)>>1;  
        int m_r = (mid+b)>>1;  
        //构建四个子树   
        root->child[0] = dfs( word, move, a, m_l );  
        root->child[1] = dfs( word, move, m_l+1, mid );  
        root->child[2] = dfs( word, move, mid+1, m_r );  
        root->child[3] = dfs( word, move, m_r+1, b );  
    }else if ( root->color == 'f' ) {  
        //叶子节点染色   
        for ( int i = a ; i <= b ; ++ i )  
            Color[i] = 1;  
    }return root;  
}  
  
int main()  
{  
    int  n,move;  
    char data[1366];  
      
    while ( ~scanf("%d",&n) )  
    for ( int i = 0 ; i < n ; ++ i ) {  
        for ( int i = 0 ; i < 1024 ; ++ i )  
            Color[i] = 0;  
          
        //处理图片1   
        scanf("%s",data);  
        Count = 0;  
        dfs( data, move = 0, 0, 1023 );  
          
        //处理图片2   
        scanf("%s",data);  
        Count = 0;  
        dfs( data, move = 0, 0, 1023 );  
          
        //统计黑色节点   
        int sum = 0;  
        for ( int i = 0 ; i < 1024 ; ++ i )  
            sum += Color[i];  
        printf("There are %d black pixels.\n",sum);  
    }  
      
    return 0;  
}

补充：软件开发 , C++ ,