UVa297 Quadtrees

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

概要
画像が４分木を用いてモノクロで入力される。２種の画像を合わせたときに塗られたピクセルはいくつあるか

解法
１次元配列の 4*深さ+i (1<= i <= 4) の位置に４分木を埋めていく。
深さに対応したピクセルの数を配列で持っておくと便利。４のべき乗の配列になる。

反省
4のべき乗の配列は 4^5, 4^4, ..., 4^1, 4^0 まで作るけど、4^1 = 4 を書き忘れていた。0乗も含めて要素が6個あるのに、5乗のイメージがついていたせいで要素が5個で正しいと思い込んでいた。

また、algorithm の fill() を使って提出したら謎の Compilation Error に悩まされたので仕方なく memset した。
（EMPTY が 0 や -1 でないと memset は使えないので）

#include <bits/stdc++.h>

using namespace std;

int const MAX = 1000000;

enum { EMPTY, FILLED, PARENT };
int fld[MAX];
int pos;

int num[] = {1024, 256, 64, 16, 4, 1};

void rec(string const&s, int idx) {

  if(s[pos] == 'p') {
    pos++;
    for(int i=1; i<=4; i++) {
      if(fld[idx] != FILLED) fld[idx] = PARENT;
      rec(s, 4*idx+i);
    }
  }
  else if(s[pos] == 'f') {
    pos++;
    fld[idx] = FILLED;
  }
  else {
    pos++;
  }
}

int traverse(int idx, int depth) {
  
  int res = 0;
  
  if(fld[idx] == FILLED) {
    res += num[depth];
  }
  else if(fld[idx] == PARENT) {
    for(int i=1; i<=4; i++) {
      res += traverse(4*idx+i, depth+1);
    }
  }
  
  return res;
}

int main() {
  
  int Tc;
  while(cin >> Tc) {
    string s, t;
    while(Tc--) {
      cin >> s >> t;
      
      memset(fld, EMPTY, sizeof(fld)); // EMPTY = 0
      pos = 0; rec(s, 0);
      pos = 0; rec(t, 0);
      
      cout << "There are " << traverse(0, 0) << " black pixels.\n";
    }
  }
  
  return 0;
}