UVA 297 Quadtrees （4叉樹）

~~~題目連結～～

題目大意：根據題目的要求可以把矩形（32*32）轉換成4叉樹， 現在給出2個矩形， 2個矩形相加求出第三個矩形，然後求第三個矩形黑色像素所占的面積。 

code：

#include <iostream>
using namespace std;




typedef struct node
{
    char ch;
    struct node *nt[4];
}Node;


int ans = 0;


void build(int &cur, Node *r, string &s)
{
    int flag = 0;
    r->ch = s[cur++];
    for(int j = 0; j<4 && cur<s.size(); j++)
    {
        r->nt[j] = new Node;
        if(s[cur] == 'p')
        {
            build(cur, r->nt[j], s);
            continue;
        }
        r->nt[j]->ch = s[cur++];
    }
}




void query(Node *r1, Node *r2, int cur)
{
    if(r1->ch == 'p' && r2->ch == 'p')
        for(int i = 0; i<4; i++)
            query(r1->nt[i], r2->nt[i], cur*2);
    else if(r1->ch == 'f' || r2->ch == 'f')
        ans += (32/cur)*(32/cur);
    else if(r1->ch == 'e' && r2->ch == 'p')
        for(int i = 0; i<4; i++)
            query(r1, r2->nt[i], cur*2);
    else if(r1->ch == 'p' && r2->ch == 'e')
        for(int i = 0; i<4; i++)
            query(r1->nt[i], r2, cur*2);
}


int main()
{
    int t = 0, cur = 0;
    string s1, s2;
    cin>>t;
    while(t--)
    {
        cin>>s1>>s2;
        ans = 0;
        Node *r1 = new Node;
        Node *r2 = new Node;
        cur = 0;
        build(cur, r1, s1);
        cur = 0;
        build(cur, r2, s2);
        query(r1, r2, 1);
        cout<<"There are "<<ans<<" black pixels."<<endl;
    }
    return 0;
}