quadtree

http://en.wikipedia.org/wiki/Quadtree

UVa problem: 297: Quadtrees

refer to forum: http://acm.uva.es/board/viewtopic.php?f=2&t=700&p=2691&hilit=297&sid=156699fafa75aaeacf281e1af3a8006c#p2691

#include <iostream>

#define M 32
int p[M];
int idx;

int mask[] = {
  0, 0x1, 0x3, 0, // 0-3
  0xf, 0, 0, 0, 0xff, //4-8
  0,0,0,0,0,0,0,0xffff, // 16
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0xffffffff // 32
};

#ifndef ONLINE_JUDGE
// couting 1's
int count_bit(int n) {
    int bits = 0;
    while(n) {
        n &= n-1;
        ++bits;
    }
    return bits;
}
#endif

void color (char *str, int size, int x, int y) {
  if (str[idx] == 'p') {
    idx ++;
    int sz = size>>1;
    color(str, sz, x+sz, y);
    color(str, sz, x, y);
    color(str, sz, x, y+sz);
    color(str, sz, x+sz, y+sz);
  }
  else if (str[idx] == 'f') {
    idx ++;
    for (int i = y; i < y + size; i ++)
      p[i] |= mask[size] << x;
  }
  else idx++;
}
int main () {
  int num;
  char tree1[1500], tree2[1500];

  scanf("%d\n", &num);
  while(num--) {
    scanf("%s\n%s\n", tree1, tree2);

    memset(p, 0, sizeof(p));

    idx=0;
    color(tree1, M, 0, 0);

    idx=0;
    color(tree2, M, 0, 0);

    int total = 0;
    for (int i = 0; i < M; i ++)
#ifndef ONLINE_JUDGE
      total += count_bit(p[i]);
#else
      total += __builtin_popcount(p[i]);
#endif

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

UVa problem: 752 - Unscrambling Images

#include <iostream>
#include <deque>
using namespace std;
int q[16][16];
int e[16][16]; // encrypted

int d[16][16]; // decoded
inline int getxy(int size, int k, int &x, int &y) {

  deque<int> Q;
  while(k > 0) {
    int r = k % 4;
    if (r == 0) {
      r = 4;
      k = (k-4) >> 2;
    } else
      k = k >>2;

    Q.push_front(r);
  }

  x = 0, y = 0;
  for(int i = 0; i < Q.size(); ++i) {
    size = size >> 1;
    int idx = Q[i];

    if (idx == 2)
      y += size;
    if (idx == 3)
      x += size;
    if (idx == 4) {
      x += size;
      y += size;
    }
  }
  return size;
}

int main() {
  int ndata;
  scanf("%d ", &ndata);
  int nd = 1;
  while(nd <= ndata) {
    if(nd > 1) printf("\n");
    printf("Case %d\n\n", nd++);
    int n;
    scanf("%d ", &n);

    // quadtree reset to all 0
    memset(q, 0, sizeof(q));

    int m; // number of leaf nodes

    scanf("%d ", &m); 
    int k;
    int intensity;
    for(int i = 0; i < m; ++ i) {
      scanf("%d %d ", &k, &intensity);
      int x, y;
      int size = getxy(n, k, x, y);

      for(int i = x; i < x+size; ++i)
        for(int j = y;j < y+size; ++j)
          q[i][j] = intensity;      
    }
/*
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j)
        printf("%4d", q[i][j]);
      printf("\n");
    }
    printf("\n");
*/
    scanf("%d ", &m);

    // encrypted quadtree reset to all 0
    memset(e, 0, sizeof(e));
    for(int i = 0; i < m; ++ i) {
      scanf("%d %d ", &k, &intensity);
      int x, y;
      int size = getxy(n, k, x, y);

      for(int i = x; i < x+size; ++i)
        for(int j = y;j < y+size; ++j)
          e[i][j] = intensity;
    }

    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j) {
        int x = q[i][j] / n;
        int y = q[i][j] % n;
        d[x][y] = e[i][j];
      }
    }
    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j)
        printf("%4d", d[i][j]);
      printf("\n");
    }
  }
}