2446 Chessboard//MaxMatch

Chessboard
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 6073
 
Accepted: 1886
Description
Alice and Bob often play games on chessboard. One day, Alice draws a board with size M * N. She wants Bob to use a lot of cards with size 1 * 2 to cover the board. However, she thinks it too easy to bob, so she makes some holes on the board (as shown in the figure below).
We call a grid, which doesn’t contain a hole, a normal grid. Bob has to follow the rules below:
1. Any normal grid should be covered with exactly one card.
2. One card should cover exactly 2 normal adjacent grids.
Some examples are given in the figures below:
A VALID solution.
An invalid solution, because the hole of red color is covered with a card.
An invalid solution, because there exists a grid, which is not covered.
Your task is to help Bob to decide whether or not the chessboard can be covered according to the rules above.
Input
There are 3 integers in the first line: m, n, k (0 < m, n <= 32, 0 <= K < m * n), the number of rows, column and holes. In the next k lines, there is a pair of integers (x, y) in each line, which represents a hole in the y-th row, the x-th column.
Output
If the board can be covered, output "YES". Otherwise, output "NO".
Sample Input

4 3 2
2 1
3 3

Sample Output

YES

Hint
A possible solution for the sample input.
Source
POJ Monthly,charlescpp
 
 
제목은 1*2의 매트릭스로 매트릭스를 덮어쓸 수 있다는 거예요.
이어서 최소 라인 덮어쓰기
 
#include#includeint n,m,k;bool map[35][35];int mat[1050][1050],link[1050];;bool used[1050];int dx[4]= {0,0,-1,1};int dy[4]= {-1,1,0,0};bool can(int t){    int x,y,xx,yy;    x=(t-1)/m+1;    y=(t-1)%m+1;   //for(int i=1;i<=m*n;i++)    for(int k=0; k<=4; k++)    {        xx=x+dx[k];        yy=y+dy[k];        if(xx>0&&xx<=n&&yy>0&&yy<=m&&map[xx][yy]==false)        {           int i=(xx-1)*m+yy;           if(used[i]==false&&mat[t][i])           {              used[i]=true;              if(link[i]==-1||can(link[i]))              {                link[i]=t;                return true;              }           }        }    }    return false;}int MaxMatch(){    memset(link,-1,sizeof(link));    int num=0;    for(int i=1; i<=m*n; i++)    {        memset(used,false,sizeof(used));        if(can(i))        {            num++;           //printf("%d/n",i);        }    }    return num;}int main(){    while(scanf("%d%d%d",&n,&m,&k)!=EOF)    {        int num=0;        bool flag=false;        memset(map,false,sizeof(map));        for(int i=1; i<=k; i++)        {            int x,y;            scanf("%d%d",&y,&x);            map[x][y]=true;        }        memset(mat,false,sizeof(mat));        for(int i=1; i<=n; i++)            for(int j=1; j<=m; j++)                if(map[i][j]==false)                {                    num++;                    int cas=0;                    for(int k=0; k<4; k++)                    {                        int xx=i+dx[k];                        int yy=j+dy[k];                        if(xx>0&&xx<=n&&yy>0&&yy<=m&&map[xx][yy]==false)                        {                            mat[(i-1)*m+j][(xx-1)*m+yy]=true;                            cas++;                        }                    }                    if(cas==0) flag=true;                }        if(flag) printf("NO/n");        else if(MaxMatch()==num) printf("YES/n");        else printf("NO/n");    }    return 0;}