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; }
結構すんなりできた。だいぶマッチングはわかってきたかな。