[UVA] 297 - Quadtrees

/* 題目: UVa 297 - Quadtrees
 * Language: C++
 * Created on: 2016年3月26日
 *   Author: hanting
 */
#include <iostream>
using namespace std;
int stri = 1;
void build(bool *table, string str, int index)
{
    if(stri < str.size())
    {
        for(int i = 1; i <= 4; i++)
        {
            if(str[stri] == 'p')
            {
                stri++;
                table[index+i] = 0;
                build(table, str, 4*(index+i));
            }
            else if(str[stri] == 'e')
            {
                stri++;
                table[index+i] = 0;
            }
            else // if(str[stri] == 'f')
            {
                stri++;
                table[index+i] = 1;
            }
        }
    }

}
int value(bool *table, int index)
{
    if(index < 2048)
    {
        if(table[index])
        {
            if(index == 0) return 1024;
            else if(index <= 4) return 256;
            else if(index <= 20) return 64;
            else if(index <= 84) return 16;
            else if(index <= 340) return 4;
            else return 1;
        }
        else
        {
            int subIndex = index*4;
            int sum = 0;
            for(int i = 1; i <= 4; i++)
            {
                sum += value(table, subIndex+i);
            }
            return sum;
        }
    }
    return 0;
}
int main()
{
    int testCase = 0;
    cin >> testCase;
    while(testCase--)
    {
        stri = 1;
        bool table1[2048] = {0};
        bool table2[2048] = {0};

        string str1, str2;
        cin >> str1 >> str2;
        if(str1[0] == 'p')
            build(table1, str1, 0);
        else
            table1[0] = str1[0] == 'f';

        stri = 1;
        if(str2[0] == 'p')
            build(table2, str2, 0);
        else
            table2[0] = str2[0] == 'f';

        for(int i = 0; i < 2048; i++)
        {
            table1[i] = table1[i] or  table2[i];
        }
        cout << "There are " << value(table1, 0) << " black pixels." << endl;
    }

    return 0;
}