Muddy Fields

原题去我创的专题里找，在文件夹首页。

题目：

给出N*M矩阵。当中*表示泥土，.表示小草。要你用最少的木板把泥土覆盖。

木板长度不限。可是仅仅能水平和竖直。

行列式二分匹配配。是poj3041建图的加强版。

算法：

由poj3041的建图能够得到灵感。即把木板当作顶点，X轴，Y轴当作边。求解最小顶点覆盖。

3041的激光束不存在障碍物的问题，而这题却有不能压坏小草的限制。

我们能够换个角度思考。既然不能压坏小草，那就相当于该激光束到达这里必须停止了。

所以，我们就以小草为界分块的进行建图分析。

每当遇到了小草就到做是行或者是列到头了。

这样一来就是普通的二分图了。

T_T这一题的数据是25*25是上限 。由于。最坏情况下是草和泥土相间出现。

还有就是以后做题的时候，特别是矩阵输入一定要注意输入行列问题！！

！！！

。！！

！

说多了都是泪啊！！。！

/*

    把对行列覆盖的木板当作点。则每一个格子变成了边。

    则问题转换成了最小顶点覆盖问题

*/

#include <iostream>

#include <algorithm>

#include <vector>

#include <cstdio>

#include <cstring>

using namespace std;

const int MAXN = 50 + 10;

const int MAXV = 1500;

vector<int> G[MAXV];

char mp[MAXN][MAXN];

int numx[MAXN][MAXN],numy[MAXN][MAXN];

int match[MAXV];

bool used[MAXV];

int N,M,V;

void init(){

    for(int i = 0;i <= N*M;++i)

        G[i].clear();

}

bool dfs(int u){

   for(int i = 0;i < (int)G[u].size();++i){

       int v = G[u][i];

       if(!used[v]){

           used[v] = 1;

           if(match[v] == -1||dfs(match[v])){

               match[v] = u;

               return true;

           }

       }

   }

   return false;

}

void solve(){

    int res = 0;

    memset(match,-1,sizeof(match));

    for(int i = 1;i <= V;++i){

        memset(used,0,sizeof(used));

        if(dfs(i)) res++;

    }

    printf("%d\n",res);

}

int main()

{

   // freopen("Input.txt","r",stdin);

    while(~scanf("%d%d",&N,&M)){

         init();

         for(int i = 0;i < N;++i){

            scanf("%s",mp[i]);

         }

         int cnt = 0;

         memset(numx,0,sizeof(numx));

         memset(numy,0,sizeof(numy));

         for(int i = 0;i < N;++i)

            for(int j = 0;j < M;++j)

                 if(mp[i][j] == '*'){

                     ++cnt;

                     while(j < M&&mp[i][j] == '*'){

                        numx[i][j] = cnt;

                        ++j;

                     }

                 }

         V = cnt;

         for(int j = 0;j < M;++j)

            for(int i = 0;i < N;++i)

                if(mp[i][j] == '*'){

                    ++cnt;

                    while(i < N&&mp[i][j] == '*'){

                        numy[i][j] = cnt;

                        ++i;

                    }

                }

         for(int i = 0;i < N;++i){

            for(int j = 0;j < M;++j){

                if(numx[i][j] && numy[i][j]){

                    G[numx[i][j]].push_back(numy[i][j]);

                }

            }

         }

         solve();

    }

    return 0;

}