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 }

나의 사고방식은 대체로 이렇다.
바둑판을 두 구역에 인접하여 덮는 것이기 때문에 바둑판의 흑백을 서로 칠한 다음에 상응하는 구멍을 파서 흰색을 이분도 노드의 서브집합으로 하고 나머지는 다른 서브집합으로 한다. 그리고 인접한 흑백 블록이 대표하는 정점을 이분도에 연결한 다음에 이분도의 액수 최대 일치수를 구하면 가장 많이 놓을 수 있는 판이다.