POJ 2446 Chessboard解题报告

一、问题描述

二、解题思路

将问题转化为二分图最大匹配问题。将棋盘按国际象棋棋盘那样添上黑白两种颜色，这样的话，黑色和白色的格子就构成了二分图的两个集合，即相邻的两个格子不会属于同个集合的。然后从上到下，从左到右对格子进行编号（除了洞）,相邻的两格用边相连就构成一个二分图。如下图所示。接着对二分图求最大匹配数sum，如果sum等于(m*n-k)/2，则可以覆盖，输出YES，否则输出NO。

 

三、代码

#include<iostream>
using namespace std;
bool g[1200][1200];
int link[1200];
int b[35][35];//存储棋盘格子的类型 -1，-2分别表示二分图的两个集合，-3表示空洞
bool bb[1200];//是否已经使用
int N;//棋盘总格子数
int m,n,k;
int incY;//二分图右边集合元素数目
int incX;//二分图左边集合元素数目
//二分图最大匹配算法
bool find(int a)
{
    int i;
    for(i=1;i<=incY;++i)
    {
        if( bb[i]==false && g[a][i]==1 )
        {
            bb[i]=true;
            if( link[i]==0 || find(link[i]) )
            {
                link[i]=a;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    int i,j;
    int x,y;
    scanf("%d%d%d",&m,&n,&k);
    memset(b,-1,sizeof(b));//

    memset(link,0,sizeof(link));
    memset(g,0,sizeof(g));
    N=m*n;
    for(i=1;i<=k;++i)
    {
        scanf("%d%d",&x,&y);
        b[y][x]=-3;//表示有洞

    }
    if((N-k)%2==1)
    {
        printf("NO\n");
        return 0;
    }
    incY=0;
    for(i=1;i<=m;++i)
    {
        if(i%2==0)//
            j=1;
        else
            j=2;
        for(;j<=n;j+=2)
        {
            if(b[i][j]!=-3)
            {
                ++incY;
                b[i][j]=incY;
            }
        }
    }
    incX=0;
    for(i=1;i<=m;++i)
    {
        if(i%2==1)
            j=1;
        else
            j=2;
        for(;j<=n;j+=2)
        {
            if(b[i][j]==-1)
            {
                ++incX;
                b[i][j]=incX;
                if(j>1 && b[i][j-1] != -3)
                    g[ b[i][j] ][ b[i][j-1] ]=true;

                if(j<n && b[i][j+1] != -3)
                    g[ b[i][j] ][ b[i][j+1] ]=true;

                if(i>1 && b[i-1][j] !=-3)
                    g[ b[i][j] ][ b[i-1][j] ]=true;

                if(i<m && b[i+1][j] !=-3)
                    g[ b[i][j] ][ b[i+1][j] ]=true;
            }
        }
    }
    int sum=0;
    for(i=1;i<=incX;++i)
    {
        memset(bb,0,sizeof(bb));
        if( find(i) )
            sum++;
    }
    if(sum == ((N-k)/2))
        printf("YES\n");
    else
        printf("NO\n");