PKU 1610 Quad Trees

http://poj.org/problem?id=1610
白黒の画像データを、同じ部分をまとめて符号化して出力するというような問題。

再帰。
結構時間ギリギリでした

bool in[512][512];
map<int,vector<int> > ans;

void dfs(int x,int y,int n){
  set<bool> app;
  rep(i,n)rep(j,n)app.insert(in[x+i][y+j]);
  if(app.size()==1)ans[-n].pb(0),ans[-n].pb(*app.begin());
  else{
    ans[-n].pb(1);
    dfs(x,y,n/2);
    dfs(x,y+n/2,n/2);
    dfs(x+n/2,y,n/2);
    dfs(x+n/2,y+n/2,n/2);
  }
}

main(){
  int t;
  cin>>t;
  while(t--){
    ans.clear();
    int n;
    cin>>n;
    rep(i,n)rep(j,n)cin>>in[i][j];
    dfs(0,0,n);
    vector<int> vec;
    FOR(miter,ans)vec.insert(vec.end(),ALL(miter->S));
    reverse(ALL(vec));
    string out;
    rep(i,SZ(vec)){
      int p=0;
      rep(j,4){
        if(i+j<SZ(vec))p+=vec[i+j]<<j;
      }
      i+=3;
      if(p<9)out+=(p+'0');
      else out+=(p-10+'A');
    }
    reverse(ALL(out));
    cout<<out<<endl;
  }
}