POJ 2226 Muddy Fields 二分图(难点在于建图)

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：给定一个矩阵和它的N行M列,其中有一些地方有水,现在有一些长度任意,宽为1的木板，要求在板不跨越草，用一些木板盖住这些有水的地方,问至少需要几块板子？

思路：首先想到如果没有不准跨越草的条件则跟POJ 3041题意一样(如果想看的话可以点击这里)，然而这一题多了个条件，那么将矩阵转化的方式需要改变，不能直接将行列分成两个集合了。需要先查看两遍矩阵，一遍横向查看有无连续‘*’的情况，若连续说明一块板子就可以覆盖，所以标记为同样的数字，反之则不同；同理另一遍纵向查看矩阵连续'*'的情况，处理方式同上。这样就建图完毕了。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = ; int n, m, p, q; bool lin[N][N]; int used[N], arr[N], mark[N][N]; char map[N][N]; bool find(int x) { for(int j = ; j <= q; j++) { if(lin[x][j] && used[j] == ) { used[j] = ; if(arr[j] == || find(arr[j])) { arr[j] = x; return true; } } } return false; } int main() { int r, c; while(~scanf("%d%d", &n, &m)) { memset(map, '', sizeof(map)); for(int i = ; i < n; i++) { scanf("%s", &map[i]); } memset(lin, false , sizeof(lin)); memset(arr, , sizeof(arr)); p = ; for(int i = ; i < n; i++) { for(int j = ; j < m; j++) { if(map[i][j] == '*') { if(map[i][j-] != '*')//横向查看 { p++; } mark[i][j] = p; } } } q = ; for(int j = ; j < m; j++) { for(int i = ; i < n; i++) { if(map[i][j] == '*') { if(map[i-][j] != '*')//纵向查看 { q++; } lin[mark[i][j]][q] = true;//横向已经检查完了可以直接建图了 } } } int all = ; for(int i = ; i <= p; i++) { memset(used, , sizeof(used)); if(find(i)) ++all; } printf("%d\n", all); } return ; }