uva_297-Quadtrees

2014-11-24 10:21:40 · 作者: · 浏览: 0
[cpp]
/**总共是1024像素,递归建立4叉树,然后统计黑格子数量即可
*解决,我这里是模拟建立4叉树,能达到同样的效果,而且能
*节省一点时间和空间
*/ www.2cto.com
#include
#include
#include
using namespace std;

#define MAX 1024
#define POS 4

bool a[MAX+2];

void pre_create_tree(int l, int r, int n){
char c;
while(scanf("%c", &c), isspace(c));
if( c == 'p' ){
for(int i = 0; i < POS; i ++){
if( i ) l += n/POS;
pre_create_tree(l, l+n/POS-1, n/POS);
}
}else if( c == 'f' ){
for(int i = l; i <= r; i ++) a[i] = true;
}else return ;
}

int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
#endif
int cas, sum;
scanf("%d", &cas);
while( cas-- ){
sum = 0;
for(int i = 1; i <= MAX; i ++) { a[i] = false;}
pre_create_tree(1, 1024, 1024);
pre_create_tree(1, 1024, 1024);
for(int i = 1; i <= MAX; i ++)
if( a[i] ) sum ++;
printf("There are %d black pixels.\n", sum);
}
return 0;
}