POJ 2226 Muddy Fields 二分图巧妙建图 + 二分图最大匹配

Rain has pummeled the cows' field, a rectangular grid of R rows and C columns (1 <= R <= 50, 1 <= C <= 50). While good for the grass, the rain makes some patches of bare earth quite muddy. The cows, being meticulous grazers, don't want to get their hooves dirty while they eat. 

To prevent those muddy hooves, Farmer John will place a number of wooden boards over the muddy parts of the cows' field. Each of the boards is 1 unit wide, and can be any length long. Each board must be aligned parallel to one of the sides of the field. 

Farmer John wishes to minimize the number of boards needed to cover the muddy spots, some of which might require more than one board to cover. The boards may not cover any grass and deprive the cows of grazing area but they can overlap each other. 

Compute the minimum number of boards FJ requires to cover all the mud in the field.

Input

* Line 1: Two space-separated integers: R and C 

* Lines 2..R+1: Each line contains a string of C characters, with '*' representing a muddy patch, and '.' representing a grassy patch. No spaces are present.

Output

* Line 1: A single integer representing the number of boards FJ needs.

Sample Input

4 4
*.*.
.***
***.
..*.

Sample Output

4

Hint

OUTPUT DETAILS: 

Boards 1, 2, 3 and 4 are placed as follows: 
1.2. 
.333 
444. 
..2. 
Board 2 overlaps boards 3 and 4.

分别 按行扫描  按列扫描   出来两个 系列 板子号    然后每个坑洼处都是一条边  连接两个系列的板子   这样 只要把所有的边用最少的点都覆盖上就好了   

最小点覆盖 = 最大匹配

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<string>
#include<cmath>
#define ff(i,x,y) for(int i=x;i<y;i++)
#define maxlen 2500+7
#define maxlen2 50+7
using namespace std;
bool mp[maxlen2][maxlen2];//原始的map图  0表示草地 1表示坑
int mp1[maxlen2][maxlen2];//按行扫描得出来的木板点图 序号表示应该是第几个板子
int mp2[maxlen2][maxlen2];//按列扫描  同上
vector<int> relmmap[maxlen];//板子点 的有边相连相关 板子点
int n;
int m;
bool check[maxlen];
int matching[maxlen];
bool dfs(int u)//匈牙利算法 dfs
{
for(int i = 0; i < relmmap[u].size(); i++)
{
int newpos = relmmap[u][i];
if(check[newpos] == 0)
{
check[newpos] = 1;
if(matching[newpos] == -1 || dfs(matching[newpos]) == 1)
{
matching[newpos] = u;
return true;
}
}
}//for
return false;
}
int main()
{
//freopen("test.txt", "r", stdin);
scanf("%d %d", &n, &m);
//input
for(int i = 0; i < n; i++)
{
char x[maxlen];
scanf("%s", x);
for(int j = 0; j < m; j++)
{
if(x[j] == '.')
mp[i][j] = 0;
else
{
mp[i][j] = 1;
}
}
}//for

//construct graph

//按行扫描
int key = 0;//保存行扫描出的点数量
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(mp[i][j] == 1)
{
mp1[i][j] = ++key;
while(++j < m && mp[i][j])
mp1[i][j] = key;
}
//按列扫描
int key2 = 0;//保存列扫描出的点的数量
for(int j = 0; j < m; j++)
for(int i = 0; i < n; i++)
if(mp[i][j] == 1)
{
mp2[i][j] = ++key2;
while(++i < n && mp[i][j])
mp2[i][j] = key2;
}
//构造图
for(int i = 0; i < key; i++)
relmmap[i].clear();//ini
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(mp1[i][j] != 0 && mp2[i][j] != 0)
relmmap[mp1[i][j]].push_back(mp2[i][j]);
}
//do 匈牙利
int ans = 0;
memset(matching, -1, sizeof matching);
for(int i = 1; i <= key; i++)
{
memset(check, 0, sizeof check);
if(dfs(i) == 1)
ans++;
}
printf("%d\n", ans);
return 0;
}