TopCoder SRM 550 Div2 Hard TopView

ちょっと手こずったけど普通に回答。
http://community.topcoder.com/stat?c=problem_statement&pm=11494

問題

文字が書かれたグリッドが与えられる。
このグリッドは、1つの文字で長方形領域を埋める、という処理を繰り返して行った結果である。
（ただし、1つの文字は、1回しか利用されない）

与えられたグリッドを再現できる処理順を示せ。
また、複数そのような処理順があれば辞書順最小のものを示せ。

解法

各文字に対応する長方形領域は、グリッド上に登場するその文字を囲う最小の長方形と考えることができる。

次に、各文字に処理された前後順を判定する。
前後順は、ある文字の長方形領域の上に他の文字があれば、他の文字が後で埋めたと考えることができる。

あとは、各文字の前後関係と矛盾がない範囲で各文字を並べ、辞書順最小化すればよい。
この処理は未使用文字を小さい順に見て、処理前後順で前のものが内容な文字を選んでいけばよい。

グラフでいうと、前後関係を辺で表したとき、inbound辺がない順に頂点を拾っていけばよいといえる。

int L[256],R[256],T[256],B[256],N[256],CN;
int over[256][256];

class TopView {
	public:
	int H,W;
	string findOrder(vector <string> grid) {
		int y,x,i;
		
		CN=0;
		H=grid.size();
		W=grid[0].size();
		set<char> S;
		FOR(i,256) L[i]=T[i]=100,R[i]=B[i]=-1,N[i]=0;
		
		FOR(y,H) FOR(x,W) if(grid[y][x]!='.') {
			L[grid[y][x]] = min(L[grid[y][x]],x);
			R[grid[y][x]] = max(R[grid[y][x]],x);
			T[grid[y][x]] = min(T[grid[y][x]],y);
			B[grid[y][x]] = max(B[grid[y][x]],y);
			N[grid[y][x]]++;
			CN++;
		}
		ZERO(over);
		ZERO(inb);
		FOR(i,256) if(N[i]) {
			for(y=T[i];y<=B[i];y++) for(x=L[i];x<=R[i];x++) {
				if(grid[y][x]=='.') return "ERROR!";
				if(grid[y][x]!=i) over[i][grid[y][x]]=1;
			}
		}
		
		string res;
		while(1) {
			FOR(i,256) if(N[i]) {
				int ng=0;
				FOR(x,256) ng |= (N[x] && over[x][i]);
				if(ng==0) break;
			}
			if(i==256) break;
			
			res += (char)i;
			CN -= N[i];
			N[i]=0;
		}
		
		if(CN==0) return res;
		else return "ERROR!";
	}
};

まとめ

Div2は割とオーソドックスな問題が多いよね。