棋盘覆盖
给定一个N行N列的棋盘，已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为2、宽度为1的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。
输入格式
第一行包含两个整数N和t，其中t为禁止放置的格子的数量。
接下来t行每行包含两个整数x和y，表示位于第x行第y列的格子禁止放置，行列数从1开始。
输出格式
输出一个整数，表示结果。
数据范围
1≤N≤100
输出样例：
8 0
输出样例：
32
题解：
之前做了一个类似的数据小的题用的状压来做的，不过这道题范围果断劝退了。
说实话二分图题做的少做的时候根本想不出二分图怎么建图。这道题是这样的。我们在矩阵中放1×2的长方形，那么我们会占两个格子，格子我们通过标出他们的x,y下标可以发现。下标和为偶数的格子四周一定被奇数包围起来了，奇数一样。所以这明显就是二分图了。我们通过偶数方格向周围奇数方格连边，相当于占用了两个格子，也就是放了一个长方形上去。那么我们边只要保证没有公共点就可以了。所以这道题就是求可以连多少条边的问题了。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1e2+7;
int ne[N],head[N],e[N],vis[N][N];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int n,t;
int g[N][N];
pii match[N][N];
bool dfs(int x,int y)
{
for(int i=0;i<4;i++){
int tx=x+dir[i][0];
int ty=y+dir[i][1];
if(tx<1||tx>n||ty<1||ty>n||g[tx][ty]||vis[tx][ty]) continue;
vis[tx][ty]=1;
pii t=match[tx][ty];
if(t.first==-1||dfs(t.first,t.second)){
match[tx][ty]={x,y};
return 1;
}
}
return 0;
}
int main()
{
cin>>n>>t;
memset(match,-1,sizeof match);
for(int i=1;i<=t;i++){
int a,b; scanf("%d%d",&a,&b);
g[a][b]=1;
}
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if((i+j)%2==0&&!g[i][j]){
memset(vis,0,sizeof vis);
if(dfs(i,j)) res++;
}
}
}
cout<<res<<endl;
}