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; } } }