原题链接
思路：
因为骨牌是1*2的，所以可以看成是两个格子放一个。
建图过程：假设格子的坐标是（i,j），那么可以根据i+j的奇偶把所有的格子分成黑白两种，如果某个黑格子没有被禁止，那么就可以让它和它周围的白格子连边。黑格子周围都不会出现黑格子，所以同一类型的格子之间是不存在边的。建图后求二分图的最大匹配即可。
代码：
#include<bits/stdc++.h> using namespace std; int g[110][110];///表示不能放置 bool st[110][110]; typedef pair<int,int>PII; PII mat[110][110]; int nx[]={0,0,1,-1}; int ny[]={1,-1,0,0}; int n,m; bool check(int x,int y){ if(x>0&&x<=n&&y>0&&y<=n&&!g[x][y]&&!st[x][y]) return 1; return 0; } bool Find(int x,int y){ for(int i=0;i<4;i++){ int nxx=x+nx[i],nyy=y+ny[i]; if(check(nxx,nyy)){ st[nxx][nyy]=1; PII t=mat[nxx][nyy]; if(t.first==-1||Find(t.first,t.second)){ mat[nxx][nyy]={x,y}; return 1; } } } return 0; } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; g[x][y]=1; } memset(mat,-1,sizeof mat); int res=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if((i+j)%2&&!g[i][j]){ memset(st,0,sizeof st); if(Find(i,j)) res++; } cout<<res<<endl; return 0; }
