2013年8月25日

UVa 297 - Quadtrees

#include <stdio.h>
#include <string.h>

char tree[9999];
int now, pix[32][32];

void travel(int r, int c, int size) {
  now++;
  if (tree[now] == 'p') {
    size >>= 1;
    travel(r, c + size, size);
    travel(r, c, size);
    travel(r + size, c, size);
    travel(r + size, c + size, size);
  } else if (tree[now] == 'f') {
    int i, j;
    for (i = r; i < r + size; i++) {
      for (j = c; j < c + size; j++) {
        pix[i][j] = 1;
      }
    }
  }
}

int main() {
  int T;
  scanf("%d", &T);
  getchar();
  while (T--) {
    memset(pix, 0, sizeof(pix));
    int num = 2;
    while (num--) {
      gets(tree);
      now = -1;
      travel(0, 0, 32);
    }
    int r, c, ans = 0;
    for (r = 0; r < 32; r++) {
      for (c = 0; c < 32; c++) {
        ans += pix[r][c];
      }
    }
    printf("There are %d black pixels.\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言