题目描述
棋盘覆盖
给定一个N行N列的棋盘，已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。
输入格式
第一行包含两个整数N和t，其中t为禁止放置的格子的数量。
接下来t行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。
输出格式
输出一个整数，表示结果。
数据范围
1 ≤ N ≤ 100 1≤N≤1001≤N≤100
输出样例：
8 0
输出样例：
32
题解
这道题看上去与二分图没有任何关系，但我们仔细想想，要满足二分图匹配的性质：
1.节点能分成两个独立的集合，每个集合内部没有边互相连接。
2.每一个节点只能与另一个集合有一条匹配边相连
我们在矩阵中放1×2的长方形，那么我们会占两个格子，格子我们通过标出他们的x,y下标可以发现。下标和为偶数的格子四周一定被奇数包围起来了，奇数一样。所以这明显就是二分图了。我们通过偶数方格向周围奇数方格连边，相当于占用了两个格子，也就是放了一个长方形上去。那么我们边只要保证没有公共点就可以了。所以这道题就是求可以连多少条边的问题了。
我们根据这个性质，建立一个二维的二分图匹配
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=300;
int n,t,ans;
int g[N][N];
pair<int,int>match[N][N];
int vis[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool find(int x,int y)
{
for(int i=0;i<4;i++)
{
int a=x+dx[i];
int b=y+dy[i];
if(a<=0||b<=0||a>n||b>n) continue;
if(g[a][b]) continue;
if(vis[a][b]) continue;
pair<int,int> t=match[a][b];
if(!vis[a][b])
{
vis[a][b]=1;
if(!t.first||find(t.first,t.second))
{
match[a][b]={x,y};
return true;
}
}
}
return false;
}
int main()
{
cin>>n;
cin>>t;
for(int i=1;i<=t;i++)
{
int x,y;
cin>>x>>y;
g[x][y]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if((i+j)%2&&!g[i][j])
{
memset(vis,0,sizeof vis);
if(find(i,j)) ans++;
}
}
}
cout<<ans;
}