TopCoder SRM 527 Div1 Medium P8XMatrixRecovery

問題

'0'と'1'からなる行列が隠されている。
それぞれの行ごとの情報がrowsにより与えられる。
rows[i][j]は'0','1'はそれぞれの成分が'0','1'であることをあらわし、
'?'は未確定なことをあらわす。


列ごとの情報がcolumnsにより与えられる。
列ごとの情報は、行ごとの情報と同様の形式で与えられるが、列の順序が入れ替わっていることがある。


元の行列としてありえるもののうち、辞書順で最小のものを求めよ。

制約条件

行,列≦30

方針

どの列がどの列に対応しうるかの関係をグラフにすると、
二部グラフになる。
このグラフが完全マッチングを持てば、元の行列が存在する。


左上から一つずつ'?'を見て、'0'を入れてみて完全マッチングが存在するかを確かめ、
存在するなら'0'を入れて、そうでないなら'1'を入れればよい。

ソースコード

int n,h,w;
int p[100];
bool e[100][100];
bool v[100];
bool match(int s){
	if(s<0)return 1;
	rep(i,n)if(e[s][i]&&!v[i]){
		v[i]=1;
		if(match(p[i]))return p[i]=s,p[s]=i,1;
	}
	return 0;
}
bool ok(vs &r,vs &c){
	rep(i,w)rep(j,w){
		bool ok=1;
		rep(k,h)if(r[k][i]!='?'&&c[j][k]!='?'&&r[k][i]!=c[j][k]){
			ok=0; break;
		}
		e[i][j+w]=e[j+w][i]=ok;
	}
	n=w*2;
	memset(p,-1,sizeof(p));
	int res=0;
	rep(i,w){
		rep(j,n)v[j]=0;
		if(match(i))res++;
	}
	return res==w;
}

class P8XMatrixRecovery {
	public:
	vector <string> solve(vector <string> rows, vector <string> columns) 
	{
		h=rows.size(),w=rows[0].size();
		memset(e,0,sizeof(e));
		rep(i,h)rep(j,w)if(rows[i][j]=='?'){
			rows[i][j]='0';
			if(!ok(rows,columns))rows[i][j]='1';
		}
		return rows;
	}
};