AOJ 1206 BUT We Need a Diagram

BUT We Need a Diagram
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1206

問題概要

二分木をパーズして、規則を守った最小の図示をせよ。

解法

構文解析＋分割統治？
パーズするまでは楽ちん。

ただ、図示を最小化がかなりきつい。

部分木ごとにわけ、あるノードにある部分木をできるだけ近づけるということを再帰的にやる。
部分木の各高さについてのもっとも左の場所ともっとも右の場所を保存する必要あり。

ソース

#include<iostream>
#include<string>
#include<vector>
#include<cstdlib>
 
#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
 
using namespace std;
 
const int N = 81;
 
class Node{
public:
  int y, x, width, lbase, rbase, l, r;
  char label;
  Node(){
    l = r = -1;
    width = lbase = rbase = 0;
  }
};
 
Node M[N];
string s;
int pos, minix, miniy, cnt;
vector<Node> RES[N];
void setPos(int y, int x, int id){
  Node &now = M[id];
  now.x = x - minix;
  now.y = y - miniy;
  if(now.l == -1){
    RES[y-miniy].push_back(now);
    return;
  }
  if(now.r == -1){
    setPos(y-1, x, now.l);
    RES[y-miniy].push_back(now);
    return;
  }
  setPos(y-1, x + now.lbase, now.l);
  setPos(y-1, x + now.rbase, now.r);
  RES[y-miniy].push_back(now);
}
 
vector<pair<int, int> >  setWidth(int id){
  Node &now = M[id];
  vector<pair<int, int> > ret, L, R;
  ret.push_back(make_pair(0, 0));
  if(now.l == -1){
    now.width = 0;
    return ret;
  }
  if(now.r == -1){
    L = setWidth(now.l);
    ret.insert(ret.end(), ALL(L));
    now.width = 1;
    return ret;
  }
  L = setWidth(now.l);
  R = setWidth(now.r);
  int width = 0;
  rep(i, min(L.size(), R.size())){
    width = max(width, abs(L[i].second - R[i].first)+1);
    if(i == (int)min(L.size(), R.size())-1)break;
    width = max(width, abs(L[i+1].second - R[i].first));
    width = max(width, abs(L[i].second - R[i+1].first));
  }
  if(L.size() > R.size()){
    width = max(width, abs(L[R.size()].second - R[R.size()-1].first));
  }
  if(R.size() > L.size()){
    width = max(width, abs(L[L.size()-1].second - R[L.size()].first));
  }
   
  int &lbase = now.lbase, &rbase = now.rbase;
  lbase = -width/2 -1, rbase = width/2 + 1;
  if(width%2 == 0)lbase += 1;
  rep(i, max(L.size(), R.size())){
    pair<int, int> tmp(0, 0);
    if(i < (int)L.size()){
      tmp.first = L[i].first + lbase;
      tmp.second = L[i].second + lbase;
    }
    if(i < (int)R.size()){
      tmp.first = min(R[i].first + rbase, tmp.first);
      tmp.second = max(R[i].second + rbase, tmp.second);
    }
    if(id == 0)minix = min(minix, tmp.first);
    ret.push_back(tmp);
  }
  now.width = width + 2;
  return ret;
}
 
int parse(int y){
  miniy = min(y, miniy);
  Node &node = M[cnt];
  int nowid = cnt;
  cnt++;
  node.label = s[pos];
  pos++;
  if(s[pos] != '(')return nowid;
  pos++;
  node.l = parse(y-1);
  if(s[pos] == ',')pos++;
  else {
    pos++;
    return nowid;
  }
  node.r = parse(y-1);
  pos++;
  return nowid;
}
 
int main(){
  int tc = 0;
  while(1){
    tc++;
    cout << tc << ":" << endl;
    bool end = false;
    string tmp;
    pos = 0;
    cnt = 0;
    minix = miniy = 0;
    rep(i, N){
      RES[i].clear();
      M[i] = Node();
    }
    s = "";
    while(1){
      cin >> tmp;
      s += tmp;
      if(*(tmp.end() - 1) == ';'){
    break;
      }
      if(*(tmp.end() - 1) == '.'){
    end = true;
    break;
      }
    }
    parse(0);
    setWidth(0);
    setPos(0, 0, 0);
    rep(i, N){
            if(RES[i].size() == 0)break;
       
      if(i != 0){
    int pre = 0;
    FOR(it, RES[i]){
      int lpos = it->x + it->lbase;
      if(it->width == 0)continue;
      rep(j, lpos - pre)cout << ' ';
      rep(j, it->width)cout << '-';
      pre = lpos+it->width;
    }
    cout << endl;
      }
      int pre = 0;
      FOR(it, RES[i]){
    rep(j, it->x - pre)cout << ' ';
    cout << it->label;
    pre = it->x + 1;
      }
      cout << endl;
    }
    if(end)break;
  }
  return 0;
}