PKU 2530 Tetris Alphabet

PKU

http://poj.org/problem?id=2530

アルファベット文字からなるブロックを落下させるだけのテトリスの状態が入力として与えられる。
このとき、ブロックを落下させた順として辞書順最小のものは何か答えろというような問題。

現在の状態から、できるだけ辞書順後ろの方のブロックを先に引き上げていく。
そのブロックを引き上げるときには、邪魔なブロックのうち後の方のブロックを引き上げるということを再帰的に繰り返しました。

#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define FORR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SZ(a) (int((a).size()))
#define F first
#define S second
int dx[]={0,-1,0,1,1,1,-1,-1},dy[]={1,0,-1,0,1,-1,1,-1};

bool ban[128];
string in[80];
int n;
const int r = 20;
set<char> need[128];

void cor(char ch){
  vector<PI> app;
  rep(i,n)rep(j,r) if(in[i][j]==ch) app.pb(mp(i,j));

  FOR(it,app)
    rep(i,it->F)
    if(in[i][it->S]!='.' && ch!=in[i][it->S])
      need[ch].insert(in[i][it->S]);
}

set<char> unit(set<char> a,set<char> b){
  FOR(it,b) a.insert(*it);
  return a;
}

string ans;

void dfs(set<char> s){
  FORR(it,s){
    if(ban[*it]) continue;
    ban[*it] = true;
    dfs(need[*it]);
    ans += *it;
  }
}

main(){
  cin >> n;
  rep(i,10) in[i] = string(20,'.');
  rep(i,n) cin >> in[i+10];
  n+=10;

  ban['.'] = true;

  set<char> app;
  rep(i,n)rep(j,r)if(in[i][j]!='.')
    app.insert(in[i][j]);
  
  set<char> init;
  rep(i,n)rep(j,r)if(in[i][j]!='.' && need[in[i][j]].empty()){
    init.insert(in[i][j]);
    cor(in[i][j]);
  }

  

  while(true){
    bool end = true;
    rep(i,26){
      char ch='A'+i;
      set<char> next=need[ch];
      FOR(it,need[ch]){

        next=unit(next,need[*it]);
      }
      if(SZ(next)!=SZ(need[ch])){
        end = false;
        need[ch] = next;
      }
    }

    if(end) break;
  }

  dfs(init);
  
  reverse(ALL(ans));
  cout << ans << endl;
}