POJ 2226 Muddy Fields 二分匹配

这个题的原型应该是Asteroids的变种，刚看了这道题，一眼就看出了是最小覆盖，看来我理解了最小覆盖的内在含义了。
农夫John的养牛场，是一个R 行C 列的矩形，一场大雨后，养牛场低洼的地方都有了积水。John 的牛都很娇贵的，他们吃草的时候，不想把他们的蹄子给弄脏了。为了不让牛儿们把它们的蹄子弄脏，John 决定把有水的地方铺上木板。他的木板是宽度为1，长度没有限制的。

他想用最少数目的木板把所有有水的低洼处给覆盖上，前提是木板不能覆盖草地，但是可以重叠。
Sample:
4 4
*.*.
.***
***.
..*.

把行里面连在一起的坑连起来视为一个点，即一块横木板，编上序号，Sample则转化为：

1 0 2 0
0 3 3 3
4 4 4 0
0 0 5 0

把这些序号加入X集合，再按列做一次则为：

1 0 4 0
0 3 4 5
2 3 4 0
0 0 4 0

同样加入Y集合，一个坑只能被横着的或者被竖着的木板盖住，将原图的坑的也标上不同的序号，一共九个坑

1 . 2 .
. 3 4 5
67 8 .
. . 9 .

比如7号坑可以被横着的4号木板和竖着的3号木板盖住，把每个点的对应的横木板(4)和竖木板(3)中间连一条边的话,则问题转化为找尽量少的边把这些点都盖住,根据定理便是求最大匹配数.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
    int nx, ny;             // X的點數目、Y的點數目
int mx[1000], my[1000];   // X各點的配對對象、Y各點的配對對象
bool vy[1000];           // 紀錄Graph Traversal拜訪過的點
bool adj[1000][1000];     // 精簡過的adjacency matrix

// 以DFS建立一棵交錯樹
bool DFS(int x)
{
     for (int y=0; y<ny; ++y)
         if (adj[x][y] && !vy[y])
         {
             vy[y] = true;

             // 找到擴充路徑
                if (my[y] == -1 || DFS(my[y]))
             {
                mx[x] = y; my[y] = x;
                return true;
                }
         }
     return false;
}

int bipartite_matching()
{
     // 全部的點初始化為未匹配點。
     memset(mx, -1, sizeof(mx));
        memset(my, -1, sizeof(my));

     // 依序把X中的每一個點作為擴充路徑的端點，
     // 並嘗試尋找擴充路徑。
     int c = 0;
     for (int x=0; x<nx; ++x)
//     if (mx[x] == -1)    // x為未匹配點，這行可精簡。
         {
             // 開始Graph Traversal
             memset(vy, false, sizeof(vy));
             if (DFS(x)) c++;
         }
     return c;
}
main()
{
          int a,i,j,r,c,p[51][51];
          char g[51][51];
          while(scanf("%d%d",&r,&c)!=EOF)
          {
             memset(adj, 0, sizeof(adj));
             getchar();
             for(i=0;i<r;i++)
               gets(g[i]);
             a=0;
             for(i=0;i<r;i++)
             for(j=0;j<c;j++)
             {
                if(g[i][j]!='*')
                  continue;
                else if(j==0||g[i][j-1]!='*')
                  p[i][j]=a++;
                else
                  p[i][j]=a-1;
             }
             nx=a;
             a=0;
             for(j=0;j<c;j++)
             for(i=0;i<r;i++)
             {
                if(g[i][j]!='*')
                 continue;
                else if(i==0||g[i-1][j]!='*')
                {
                 adj[p[i][j]][a]=1;
                 a++;
                }
                else
                  adj[p[i][j]][a-1]=1;
             }
             ny=a;
             printf("%d\n",bipartite_matching());
          }
          system("pause");
}