给定一个01矩阵，其中你可以在0的位置放置攻击装置。每一个攻击装置（x,y）都可以按照“日”字攻击其周围的 8个位置（x-1,y-2）,(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2),(x-2,y+1), (x+1,y+2),(x+2,y+1)
求在装置互不攻击的情况下，最多可以放置多少个装置。
BZOJ_3175_[Tjoi2013]攻击装置_二分图匹配
给定一个01矩阵，其中你可以在0的位置放置攻击装置。每一个攻击装置（x,y）都可以按照“日”字攻击其周围的 8个位置（x-1,y-2）,(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2),(x-2,y+1), (x+1,y+2),(x+2,y+1)
求在装置互不攻击的情况下，最多可以放置多少个装置。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 40050
#define M 300050
int head[N],to[M],nxt[M],cnt,n,vis[N],match[N],tot,a[220][220],idx[220][220],la;
int tx[]={-1,-2,-2,-1};
int ty[]={-2,-1,1,2};
inline void add(int u,int v) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
bool dfs(int x) {
int i;
for(i=head[x];i;i=nxt[i]) {
if(vis[to[i]]!=tot) {
vis[to[i]]=tot;
if(!match[to[i]]||dfs(match[to[i]])) {
match[to[i]]=x; return 1;
}
}
}
return 0;
}
int main() {
scanf("%d",&n);
int i,j,k,sum=0;
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
scanf("%1d",&a[i][j]);
idx[i][j]=++la;
if(a[i][j]) continue;
sum++;
for(k=0;k<4;k++) {
int di=i+tx[k],dj=j+ty[k];
if(di>=1&&di<=n&&dj>=1&&dj<=n&&!a[di][dj]) {
add(idx[i][j],idx[di][dj]);
add(idx[di][dj],idx[i][j]);
}
}
}
}
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
if(i+j&1) {
tot++;
if(dfs(idx[i][j])) sum--;
}
}
}
printf("%d\n",sum);
}
BZOJ_3175_[Tjoi2013]攻击装置_二分图匹配
原文：https://www.cnblogs.com/suika/p/9095210.html