AOJ 1220 The Devil of Gravity

The Devil of Gravity
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1220

問題概要

単語を一つのブロックとして考えるようなテキストエディタを考える。
ブロックは支えるブロックがないと、下に落ちてしまう。
そのようなテキストエディタのシミュレーションをせよ。

解法

シミュレーション。
かなり辛かった。
本番で通しきる自身がない。
もっと、簡単に実装できるかもしれない。

ソース

とても汚い。
なんとかならなかったかなぁ。

#include <string>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
using namespace std;

class Segment{
public:
  string s;
  int y, x;
};

map<pair<int, int> , int> S;
map<int, Segment> Seg;
int cy, cx, cnt;

bool valid(){
  if(S[make_pair(cy, cx)] == 0 && S[make_pair(cy, cx-1)] == 0)return false;
  return true;
}

int getid(){
  int id = S[make_pair(cy, cx)];
  if(id == 0) id =S[make_pair(cy, cx-1)];
  return id;
}

bool insertC(char c){
  int id = getid();
  if(id == 0)return false;
  string tmp;
  tmp += c;
  Seg[id].s.insert(cx - Seg[id].x, tmp);
  cx++;
  return true;
}

bool del(){
  int id = getid();
  if(cx - Seg[id].x == (int)Seg[id].s.length())return false;
  Seg[id].s.erase(cx - Seg[id].x, 1);
  if(Seg[id].s.length() == 0){
    Seg.erase(Seg.find(id));
    cy++;
  }
  return valid();
}

bool cre(){
  int id = getid();
  if(id == 0)return false;
  if(cx - Seg[id].x == (int)Seg[id].s.length())return false;
  string tmp;
  tmp += Seg[id].s[cx - Seg[id].x];
  cy--;
  id = S[make_pair(cy, cx)];
  if(id != 0)return false;
  Seg[cnt] = (Segment){tmp, cy, cx};
  cnt++;
  cx++;
  return true;
}

bool forward(){
  cx++;
  return valid();
}

bool back(){
  cx--;
  return valid();
}

bool pre(){
  cy--;
  return valid();
}

bool next(){
  cy++;
  return valid();
}

void put(){
  S.clear();
  FOR(it, Seg){
    int id = it->first, y = it->second.y, x = it->second.x;
    rep(i, Seg[id].s.length()){
      S[make_pair(y, x+i)] = id;
    }
  }
}

void move(){
  put();
  int nowid = getid();
  while(1){
    put();
    bool end = true;;
    FOR(it, S){
      if(it->second == 0)continue;
      Segment &now = Seg[it->second];
      while(1){
        int &y = now.y, &x = now.x;
        if(y == 0)break;
        bool ok = true;;
        rep(i, now.s.length()){
          if(S[make_pair(y+1, x+i)] != 0)ok = false;
        }
        if(!ok)break;
        now.y++;
        end =false;
      }
      if(!end)break;
    }
    if(end)break;
  }
  while(S[make_pair(cy, cx)] != nowid && S[make_pair(cy, cx-1)] != nowid){
    if(cy == 0)break;
    cy++;
  }
}

void merge(){
  while(1){
    put();
    bool end = true;
    FOR(it, S){
      pair<int, int> left = it->first;
      int lid = it->second;
      it++;
      if(it == S.end())break;
      pair<int, int> right = it->first;
      int rid = it->second;
      if(left.first == right.first && right.second - left.second == 1 && lid != rid){
        end = false;
        Seg[rid] = (Segment){Seg[lid].s + Seg[rid].s, Seg[lid].y, Seg[lid].x};
        Seg.erase(Seg.find(lid));
        break;
      }
      it--;
    }
    if(end)break;
  }
}

void out(){
  put();
  int id = getid();
  cout << Seg[id].s << endl; 
 
}

int main(){
  int T;
  cin >> T;
  rep(tc, T){
    S.clear();
    Seg.clear();
    cnt = 1;
    string s;
    cin >> s;
    cy = 0;
    cx = 1;
    Seg[cnt] = ((Segment){s.substr(0, 1), 0, 0});
    cnt++;
    bool flag = true;;
    REP(i, 1, s.length()){
      put();
      if(s[i] == 'F'){
        flag = forward();
      }
      else if(s[i] == 'B'){
        flag = back();
      }
      else if(s[i] == 'P'){
        flag = pre();
      }
      else if(s[i] == 'N'){
        flag = next();
      }
      else if(s[i] == 'C'){
        flag = cre();
      }
      else if( s[i] == 'D'){
        flag = del();
        put();
        move();
      }
      else {
        insertC(s[i]);
      }
      if(!flag)break;
      put();
      merge();
    }
    
    if(flag){
      out();
    }
    else {
      cout << "ERROR" << endl;
    }
  }
}