抽象为二分图,根据行列的奇偶异同性来划分左右边。
可以互相攻击的点相连(可互相攻击,必定是在异边),最多放多少不互相攻击的点,就是
在寻找二分图的最大独立集,转化为求二分图的最大匹配。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 104;
int n,m,t,ans,v[N][N],fx[N][N],fy[N][N],b[N][N];
int d[8][2] = {{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
bool check(int x,int y){
return x >= 1 && x <= n && y >= 1 && y <= m && !b[x][y];
}
int dfs(int i,int j){
for(int k = 0;k < 8;k++){
int x = i + d[k][0],y = j + d[k][1];
if(check(x,y) && !v[x][y]){
v[x][y] = 1;
if(fx[x][y] == -1 || dfs(fx[x][y],fy[x][y])){
fx[x][y] = i,fy[x][y] = j;
return 1;
}
}
}
return 0;
}
int main(){
cin>>n>>m>>t;
for(int i = 1;i <= t;i++){
int x,y;
cin>>x>>y;
b[x][y] = 1;
}
memset(fx,-1,sizeof(fx));
memset(fy,-1,sizeof(fy));
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
if(!b[i][j] && (i^j)&1){
memset(v,0,sizeof(v));
ans += dfs(i,j);
}
cout<<n*m-ans-t<<endl;
}