看到棋盘先黑白染色冷静一下
然后发现...攻击的时候同种颜色不会相互攻击
这样就是个网络流经典套路了，关于这个套路我以前好像写过几题，那边有解释一下：传送门
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e6+7,INF=1e9,xx[8]={1,2,2,1,-1,-2,-2,-1},yy[8]={2,1,-1,-2,-2,-1,1,2}; namespace Dinic { int fir[N],from[N<<2],to[N<<2],val[N<<2],cntt=1; int S,T,dep[N],Fir[N]; queue <int> Q; inline void add(int a,int b,int c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; from[++cntt]=fir[b]; fir[b]=cntt; to[cntt]=a; val[cntt]=0; } bool BFS() { for(int i=0;i<=T;i++) Fir[i]=fir[i],dep[i]=0; Q.push(S); dep[S]=1; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]||!val[i]) continue; dep[v]=dep[x]+1; Q.push(v); } } return dep[T]>0; } int DFS(int x,int mxfl) { if(x==T||!mxfl) return mxfl; int fl=0,res; for(int &i=Fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]!=dep[x]+1||!val[i]) continue; if( res=DFS(v,min(mxfl,val[i])) ) { mxfl-=res; val[i]-=res; fl+=res; val[i^1]+=res; if(!mxfl) break; } } return fl; } int dinic() { int res=0; while(BFS()) res+=DFS(S,INF); return res; } } int n,a[207][207],id[207][207],tot; char s[207]; int main() { n=read(); for(int i=1;i<=n;i++) { scanf("%s",s+1); int len=strlen(s+1); for(int j=1;j<=len;j++) { a[i][j]=(s[j]=='1'); if(!a[i][j]) id[i][j]=++tot; } } Dinic::T=tot+1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(a[i][j]) continue; if((i+j)&1) { Dinic::add(id[i][j],Dinic::T,1); continue; } Dinic::add(Dinic::S,id[i][j],1); for(int k=0;k<8;k++) { int px=i+xx[k],py=j+yy[k]; if(px<1||px>n||py<1||py>n||a[px][py]) continue; Dinic::add(id[i][j],id[px][py],INF); } } printf("%d ",tot-Dinic::dinic()); return 0; }