POJ_2446_Chessboard

题目意思就是一个M*N的有洞棋盘棋盘上，用1*2的板子去覆盖没有洞的地方，要求板子不能重叠，最终能否将棋盘完整覆盖。

代码：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<string.h>
  4 #define MAX 35
  5 
  6 struct z
  7 {
  8     int color;
  9     int ct;
 10 };
 11 struct z chess[MAX*MAX];
 12 int lc,rc;
 13 int m,n;a
 14 __int64 hole[MAX*MAX];
 15 __int64 G[MAX*MAX][MAX*MAX];
 16 __int64 link[MAX*MAX];
 17 __int64 vis[MAX*MAX];
 18 int zero=0,one=0;/*分别记录0,1的个数*/
 19 
 20 int find(int);
 21 void bin_map(void);
 22 
 23 int main(void)
 24 {
 25     int k,i,j;
 26     int x,y;
 27     scanf("%d%d%d",&m,&n,&k);
 28     for(i=0; i<k; i++)
 29     {
 30         scanf("%d%d",&x,&y);
 31         hole[n*(y-1)+x]=1;
 32     }
 33     if(n&1)
 34         for(j=1,i=1; i<=m*n; i++)
 35         {
 36             if(hole[i]==0)
 37             {
 38                 chess[i].color=j=!j;
 39                 if(j)
 40                     chess[i].ct=++one;
 41                 else
 42                     chess[i].ct=++zero;
 43             }
 44             else
 45             {
 46                 chess[i].color=-1;
 47                 j=!j;
 48             }
 49         }
 50     else
 51         for(j=1,i=1; i<=m*n; i++)
 52         {
 53             if(hole[i]==0)
 54             {
 55                 chess[i].color=!j;
 56                 if(!j)
 57                     chess[i].ct=++one;
 58                 else chess[i].ct=++zero;
 59             }
 60             else
 61                 chess[i].color=-1;
 62             if(i%n)
 63                 j=!j;
 64         }
 65     bin_map();
 66     int ans=0;
 67     for(i=1; i<=zero; i++)
 68     {
 69         memset(vis,0,sizeof(vis));
 70         if(find(i))
 71             ans++;
 72     }
 73     if(2*ans==m*n-k)
 74         puts("YES");
 75     else puts("NO");
 76     return 0;
 77 }
 78 
 79 void bin_map(void)
 80 {
 81     int i;
 82     for(i=1; i<=m*n; i++)
 83     {
 84         if(chess[i].color==0)
 85         {
 86             if(i%n!=1&&chess[i-1].color==1)
 87                 G[chess[i].ct][chess[i-1].ct]=1;
 88             if(i%n&&chess[i+1].color==1)
 89                 G[chess[i].ct][chess[i+1].ct]=1;
 90             if(i>n&&chess[i-n].color==1)
 91                 G[chess[i].ct][chess[i-n].ct]=1;
 92             if(i<=m*n-n&&chess[i+n].color==1)
 93                 G[chess[i].ct][chess[i+n].ct]=1;
 94         }
 95     }
 96 }
 97 int find(int x)
 98 {
 99     int i;
100     for(i=1; i<=one; i++)
101     {
102         if(G[x][i]&&!vis[i])
103         {
104             vis[i]=1;
105             if(link[i]==0||find(link[i]))
106             {
107                 link[i]=x;
108                 return 1;
109             }
110         }
111     }
112     return 0;
113 }

我的思路大致是这样：

由于是将棋盘相邻两区域覆盖，所以可将棋盘黑白相间的涂色，然后再挖去相应的洞，这样，将白色的作为一个二分图节点子集，剩下的作为另一个子集，然后相邻的黑白块代表的顶点在二分图中连接起来，然后求出二分图的额最大匹配数，便是最多能够放置的板子。