输入样例:
2 3 0
输出样例:
4
解析:
题意为求最大独立集,即为总点数 - 最小点覆盖。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110;
int n,m,t;
int g[N][N],vis[N][N];
pair<int,int>match[N][N];
int dir[8][2]={2,1,2,-1,1,2,1,-2,-2,1,-2,-1,-1,2,-1,-2};
int check(int x,int y){
return x>0&&y>0&&x<=n&&y<=m;
}
bool find(int x,int y){
for(int i=0;i<8;i++){
int dx=x+dir[i][0];
int dy=y+dir[i][1];
if(check(dx,dy)&&!vis[dx][dy]&&!g[dx][dy]){
vis[dx][dy]=1;
pair<int,int>p=match[dx][dy];
if(p.first==0||find(p.first,p.second)){
match[dx][dy]={x,y};
return true;
}
}
}
return false;
}
int main(){
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=t;i++){
int x,y;
scanf("%d%d",&x,&y);
g[x][y]=1;
}
int res=n*m-t;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if((i+j)%2&&!g[i][j]){
memset(vis,0,sizeof vis);
if(find(i,j)) res--;
}
}
}
cout<<res;
return 0;
}