POJ 2446 Chessboard（二维转一维+二分匹配+匈牙利算法）

迈不过友情╰ 2022-06-10 06:05 128阅读 0赞

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).  
![4510260588b39cd59a2e5a79e9306673_v_1502070969][]  
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:  
![fbad19a66a677c926c13acc9b3c05d88_v_1502070969][]  
A VALID solution.  
![d48c0b8bae885a1505438acbac2989f3_v_1502070969][]  
An invalid solution, because the hole of red color is covered with a card.  
![cbda8a0f78ee86f8b8399405d75c16a0_v_1502070969][]  
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

![a9276cb19165f895e18b937ebd50b259_v_1502070969][]  
A possible solution for the sample input.

题解：

题意：

给你个mxn大板子，同时有q个洞，你要用一些1x2的木板贴在上面且木板之间不能重复，问是否可以贴满整个板子（不能有空）

思路：

这题我没看题解居然做出来了。。做完搜一下发现思路还和他们的不一样hhhhh，貌似代码看起来也更短，用了16ms，我的思路往一个点四个方向上搜，如果不是洞就建边，但是我这里用的是二维转一维的方法，就是从右上角第一个格子开始算标号为1，然后2，3... 一直到n\*m，如果不是洞就两个标号建边，然后就直接匈牙利算法了，我用了邻接表的方法会比邻接矩阵快很多

ps:注意输入洞的下标先输入y再输入的x

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    #define INF 100861111;
    using namespace std;
    int dirx[4]={0,0,-1,1};//四个方向
    int diry[4]={1,-1,0,0};
    int p[35][35];//存洞的情况
    int n,m;
    int used[1105];//存匹配情况
    int vis[1105];
    int a[1105][5];//存邻接表，即下标为i的各种的第j个匹配的是哪个标号
    int num[1105];//存与第i个匹配有多少个格子
    int find(int u)//匈牙利算法邻接表写法
    {
        int i;
        for(i=0;i<num[u];i++)
        {
            int v=a[u][i];
            if(!vis[v])
            {
                vis[v]=1;
                if(!used[v]||find(used[v]))
                {
                    used[v]=u;
                    return 1;
                }
            }
        }
        return 0;
    }
    int main()
    {
        int i,j,k,ans,x,y,z,q;
        memset(used,0,sizeof(used));
        memset(num,0,sizeof(num));
        memset(p,0,sizeof(p));
        scanf("%d%d%d",&n,&m,&q);
        for(i=0;i<q;i++)
        {
            scanf("%d%d",&y,&x);
            p[x][y]=-1;
        }
        if((n*m-q)%2!=0)//如果剩下的格子数为奇数，肯定不符合
        {
            printf("NO\n");
            return 0;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(p[i][j]==-1)
                    continue;
                for(k=0;k<4;k++)//四个方向搞
                {
                    int xx=i+dirx[k];
                    int yy=j+diry[k];
                    if(xx>n||yy>m||xx<1||yy<1)
                        continue;
                    if(p[xx][yy]!=-1)
                    {
                        a[(i-1)*m+j][num[(i-1)*m+j]]=(xx-1)*m+yy;//这里就用了二维转一维
                        num[(i-1)*m+j]++;
                    }
                }
            }
        }
        ans=0;
        for(i=1;i<=n*m;i++)//匈牙利算法
        {
            memset(vis,0,sizeof(vis));
            if(find(i))
                ans++;
        }
        if(ans!=n*m-q)//因为这里ans为对数的两倍，所以不用除以2
        {
            printf("NO\n");
        }
        else
            printf("YES\n");
        return 0;
    }

[4510260588b39cd59a2e5a79e9306673_v_1502070969]: https://odzkskevi.qnssl.com/4510260588b39cd59a2e5a79e9306673?v=1502070969
[fbad19a66a677c926c13acc9b3c05d88_v_1502070969]: https://odzkskevi.qnssl.com/fbad19a66a677c926c13acc9b3c05d88?v=1502070969
[d48c0b8bae885a1505438acbac2989f3_v_1502070969]: https://odzkskevi.qnssl.com/d48c0b8bae885a1505438acbac2989f3?v=1502070969
[cbda8a0f78ee86f8b8399405d75c16a0_v_1502070969]: https://odzkskevi.qnssl.com/cbda8a0f78ee86f8b8399405d75c16a0?v=1502070969
[a9276cb19165f895e18b937ebd50b259_v_1502070969]: https://odzkskevi.qnssl.com/a9276cb19165f895e18b937ebd50b259?v=1502070969