POJ 2226: Muddy Fields

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

なるべく長い板を置いていく。
あとは板の縦方向の置き方と横方向の置き方を点に、草を辺に対応させて二部グラフを作り、最小点カバーを求めれば良い。

int H, W;
int N, M;
char F[60][60];
int X[60][60];
int Y[60][60];

int main() {
	scanf("%d%d", &H, &W);
	rep(i, 0, H) scanf("%s", F[i]);
	memset(X, -1, sizeof(X));
	memset(Y, -1, sizeof(Y));

	int cnt = 0;
	rep(i, 0, H) {
		int p = 0, at = 0;
		while(true) {
			if(p == W) break;
			while(at != W && F[i][at] == '*') {
				at++;
			}
			if(p == at) {
				at++; p = at;
			}
			else {
				rep(j, p, at) X[i][j] = cnt;
				cnt++;
				p = at;
			}
		}
	}
	N = cnt;
	rep(j, 0, W) {
		int p = 0, at = 0;
		while(true) {
			if(p == H) break;
			while(at != H && F[at][j] == '*') {
				at++;
			}
			if(p == at) {
				at++; p = at;
			}
			else {
				rep(i, p, at) Y[i][j] = cnt;
				cnt++;
				p = at;
			}
		}
	}
	M = cnt - N;

	int s = N + M, t = N + M + 1;
	rep(i, 0, N) MF::add_edge(s, i, 1);
	rep(j, 0, M) MF::add_edge(j + N, t, 1);
	rep(i, 0, H) 
		rep(j, 0, W) {
			if(X[i][j] != -1 && Y[i][j] != -1) {
				MF::add_edge(X[i][j], Y[i][j], 1);
			}
		}

	printf("%lld\n", MF::get(s, t));

	return 0;
}

結構すんなりできた。だいぶマッチングはわかってきたかな。