hdu 1507 Uncle Tom's Inherited Land* 【黑白染色+奇偶匹配(1X2的矩形覆盖)】

题目：Uncle Tom's Inherited Land*

题意：有一个矩阵，被分成很多小方格。有些小方格有障碍，问最多能在矩阵中

放多少1*2的矩形。

分析：黑白染色+奇偶匹配。

把格子染成国际象棋棋盘那种黑白相间。这样就能再矩阵中找出两个不相交的

点集进行二分匹配。把坐标(i,j）按照（i+j)的奇偶分类。每个格子只能与周围四个

不同颜色的匹配。这里BFS一下。然后二分匹配。

代码：

#include<cstdio>#include<iostream>#include<cstring>using namespace std;int g[105][105];int match[105][105];int vis[105][105];int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};int n,m;int f(int i,int j){    return (i-1)*m+j-1;}bool dfs(int u){    int x=u/m+1,y=u%m+1;    for(int i=0;i<4;i++)    {        int xx=x+dx[i];        int yy=y+dy[i];        if(vis[xx][yy] || g[xx][yy])            continue;        vis[xx][yy]=1;        if(match[xx][yy]==-1 || dfs(match[xx][yy]))        {            match[xx][yy]=u;            return true;        }    }    return false;}int get_max_match(){    int i,j;    int cnt=0;    for(i=1;i<=n;i++)    {        for(j=1;j<=m;j++)        {            if((i+j)%2 && g[i][j]==0)            {                memset(vis,0,sizeof(vis));                if(dfs(f(i,j)))                    cnt++;            }        }    }    return cnt;}int main(){    int k,i,j,a,b,ans;    while(scanf("%d%d",&n,&m)&&n&&m)    {        scanf("%d",&k);        memset(g,0,sizeof(g));        memset(match,-1,sizeof(match));        for(i=1;i<=k;i++)        {            scanf("%d%d",&a,&b);            g[a][b]=1;        }        for(i=0;i<=n+1;i++)  //边界处理成不能走        {                    //便于bfs时判断            g[i][m+1]=1;            g[i][0]=1;        }        for(i=0;i<=m+1;i++)          {            g[0][i]=1;            g[n+1][i]=1;        }        ans=get_max_match();        printf("%d\n",ans);        for(i=1;i<=n;i++)        {            for(j=1;j<=m;j++)            {                if(match[i][j]!=-1)                    printf("(%d,%d)--(%d,%d)\n",i,j,match[i][j]/m+1,match[i][j]%m+1);            }        }    }    return 0;}

今天写的程序全部都WA了。。。终于有个AC了。。。。我真是涕泗横流啊。。。。