UVa : 297 (Quadtrees)



// http://uva.onlinejudge.org/external/2/297.html 

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

bool pic1 [32 + 3] [32 + 3]; // true = black, false = white
bool pic2 [32 + 3] [32 + 3];
bool tmp [32 + 3] [32 + 3];
string str;

void reset ()
{
    for ( int i = 0; i < 35; i++ ) memset (tmp [i], true, sizeof (tmp [i]));
}

void copy_array (bool a [35] [35], bool b [35] [35])
{
    for ( int i = 0; i < 32; i++ ) {
        for ( int j = 0; j < 32; j++ ) a [i] [j] = b [i] [j];
    }
}

void paint_pic (int tr, int tc, int br, int bc)
{
    for ( int i = tr; i < br; i++ ) {
        for ( int j = tc; j < bc; j++ ) tmp [i] [j] = false;
    }
}

void define_child (int top_left_r, int top_left_c, int bottom_right_r, int bottom_right_c )
{
    str.erase (str.begin ());

    int tmp_top_r;
    int tmp_top_c;
    int tmp_bottom_r;
    int tmp_bottom_c;

    // pixel : 1
    tmp_top_r = top_left_r;
    tmp_top_c = (top_left_c + bottom_right_c) / 2;
    tmp_bottom_r = (top_left_r + bottom_right_r) / 2;
    tmp_bottom_c = bottom_right_c;

    if ( str [0] == 'p' ) define_child (tmp_top_r, tmp_top_c, tmp_bottom_r, tmp_bottom_c);
    else if ( str [0] == 'e' ) { paint_pic (tmp_top_r, tmp_top_c, tmp_bottom_r, tmp_bottom_c); str.erase (str.begin ()); }
    else str.erase (str.begin ());

    // pixel : 2
    tmp_top_r = top_left_r;
    tmp_top_c = top_left_c;
    tmp_bottom_r = (top_left_r + bottom_right_r) / 2;
    tmp_bottom_c = (top_left_c + bottom_right_c) / 2;

    if ( str [0] == 'p' ) define_child (tmp_top_r, tmp_top_c, tmp_bottom_r, tmp_bottom_c);
    else if ( str [0] == 'e' ) { paint_pic (tmp_top_r, tmp_top_c, tmp_bottom_r, tmp_bottom_c); str.erase (str.begin ()); }
    else str.erase (str.begin ());

    // pixel : 3
    tmp_top_r = (top_left_r + bottom_right_r) / 2;
    tmp_top_c = top_left_c;
    tmp_bottom_r = bottom_right_r;
    tmp_bottom_c = (top_left_c + bottom_right_c) / 2;

    if ( str [0] == 'p' ) define_child (tmp_top_r, tmp_top_c, tmp_bottom_r, tmp_bottom_c);
    else if ( str [0] == 'e' ) { paint_pic (tmp_top_r, tmp_top_c, tmp_bottom_r, tmp_bottom_c); str.erase (str.begin ()); }
    else str.erase (str.begin ());

    // pixel : 4
    tmp_top_r = (top_left_r + bottom_right_r) / 2;
    tmp_top_c = (top_left_c + bottom_right_c) / 2;
    tmp_bottom_r = bottom_right_r;
    tmp_bottom_c = bottom_right_c;

    if ( str [0] == 'p' ) define_child (tmp_top_r, tmp_top_c, tmp_bottom_r, tmp_bottom_c);
    else if ( str [0] == 'e' ) { paint_pic (tmp_top_r, tmp_top_c, tmp_bottom_r, tmp_bottom_c); str.erase (str.begin ()); }
    else str.erase (str.begin ());
}

int main ()
{
    int testCase;
    scanf ("%d", &testCase);

    while ( testCase-- ) {
        reset ();

        cin >> str;

        if ( str [0] == 'e' ) paint_pic (0, 0, 32, 32);
        else if ( str [0] == 'p' ) define_child (0, 0, 32, 32);

        copy_array (pic1, tmp);

        reset ();

        cin >> str;

        if ( str [0] == 'e' ) paint_pic (0, 0, 32, 32);
        else if ( str [0] == 'p' ) define_child (0, 0, 32, 32);

        copy_array (pic2, tmp);

        int cnt = 0;

        for ( int i = 0; i < 32; i++ ) {
            for ( int j = 0; j < 32; j++ ) cnt += (pic1 [i] [j] | pic2 [i] [j]);
        }

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

	return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s