Poj Solution 2446

http://poj.org/problem?id=2446

#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=1050;

int link[MAXN];
int total;

bool vist[33][33];                                                                                                //用来标记那些位置有洞
bool usedif[MAXN];
bool mat[MAXN][MAXN];

bool Can(int t)
{
     int i;
     for(i=0;i<total;i++)
      if(mat[t][i]&&!usedif[i])
      {
          usedif[i]=true;
          if(link[i]==-1||Can(link[i]))
          {
             link[i]=t;
             return true;
          }
      }
     return false;
}

int maxMatch()
{
    int i,num=0;
    memset(link,-1,sizeof(link));
    for(i=0;i<total;i++)
    {
        memset(usedif,0,sizeof(usedif));
        if(Can(i))
           num++;
    }
    return num;
}

int main()
{
    int i,j,x,y,u,t,r,c,num,ans;
    while(scanf("%d%d%d",&r,&c,&t)!=EOF)
    {
        memset(vist,0,sizeof(vist));
        for(i=0;i<t;i++)
        {
            scanf("%d%d",&y,&x);
            vist[x-1][y-1]=true;
        }
        total=r*c;
        num=total-t;
        if(num&1)                                                                                          //需要覆盖的格子数是奇数,那么不会存在可行方案
        {
             printf("NOn");
             continue;
        }
        memset(mat,0,sizeof(mat));
        for(i=0;i<r;i++)
         for(j=0;j<c;j++)
          if(!vist[i][j])
          {
               u=i*c+j;
               if((i-1)>=0&&!vist[i-1][j])
                   mat[u][(i-1)*c+j]=true;
               if((i+1)<r&&!vist[i+1][j])
                   mat[u][(i+1)*c+j]=true;
               if((j-1)>=0&&!vist[i][j-1])
                   mat[u][i*c+(j-1)]=true;
               if((j+1)<c&&!vist[i][j+1])
                   mat[u][i*c+(j+1)]=true;
          }
        ans=maxMatch();
        if(ans==num)
            printf("YESn");
        else
            printf("NOn");
    }

    return 0;
}