TopCoder SRM 505 Div1 Easy、Div2 Hard RectangleArea

Div2 Hardだと900ptでDiv1 Easyと同じ問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11400

問題

大きさHxWの長方形を、何本か辺に平行な直線で分割し、N列M行のNM個の小長方形に分割した。
i列目の小長方形の幅をX[i]、j行目の小長方形の高さをY[j]とする。

ただ、X[i]及びY[j]の値はわからない。

ここで、元の長方形の面積HxWを求めたい。
一部の小長方形の面積は判明しており、判明しているかどうかはY,Nで与えられる。
元の面積HxWを求めるのに、最小あと何個の小長方形の面積がわかればよいか求めよ。

解法

元の小長方形が以下の条件の時、全体の長方形の面積がわかる。

• 各行1個以上の小長方形の面積がわかる
• 各列1個以上の小長方形の面積がわかる
• ある行の全小長方形の面積がわかり、ある列の全小長方形の面積がわかる。

一番わかりやすいのは以下のようなケース。

YYYYY
YNNNN
YNNNN

上記の条件は相似形も成り立つ。
以下は左上3x5、右下2x4の長方形で条件を満たすが、1個'N'を'Y'にするだけで両者を連結でき、全体で5x9の長方形の面積がわかる。

YYYYYNNNN
YNNNNNNNN
YNNNNNNNN
NNNNNYYYY
NNNNNYNNN

ここまでわかると、以後以下のように求められる。

• 個々の面積判明済みの小長方形のうち、未処理のものについて以下の処理を行う。
  • DFSで同一行または同一列にある面積が判明している小長方形の位置を再帰的に求めていく。
  • DFSでたどった行および列だけからなる長方形の部分は面積が判明する。
• 判明した長方形の数-1+(未処理列数)+(未処理行数)が答え

class RectangleArea {
	public:
	int minimumQueries(vector <string> known) {
		int i,x,y;
		int H=known.size();
		int W=known[0].size();
		
		int ret=0;
		ll ymask=0,xmask=0;
		int vis[51][51];
		ZERO(vis);
		
		FOR(y,H) FOR(x,W) if(vis[y][x]==0 && known[y][x]=='Y') {
			vis[y][x]=1;
			ret++;
			queue<pair<int,int> > Q;
			Q.push(make_pair(x,y));
			while(!Q.empty()) {
				int cx=Q.front().first,cy=Q.front().second;
				Q.pop();
				ymask |= (1LL<<cy);
				xmask |= (1LL<<cx);
				
				FOR(i,H) if(known[i][cx]=='Y' && vis[i][cx]==0) vis[i][cx]=1, Q.push(make_pair(cx,i));
				FOR(i,W) if(known[cy][i]=='Y' && vis[cy][i]==0) vis[cy][i]=1, Q.push(make_pair(i,cy));
			}
		}
		
		int ly = H-__builtin_popcountll(ymask);
		int lx = W-__builtin_popcountll(xmask);
		return ret+(ly+lx-1);
	}
};

まとめ

うーん、日本語で説明しにくい問題。
コードはあまり難しくないんだけどね。