題目：http://www.lydsy.com/JudgeOnline/problem.php?id=3175

很經(jīng)典的一道騎士共存問題洗出，直接Flood fill之后網(wǎng)絡(luò)流即可骏全。

代碼：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
#define MAXN 210
#define inf 0x7fffffff
#define MAXV 50010
 
struct graph {
        
        struct edge {
               edge *next,*pair;
               int t,f;
               edge () {
                       next=pair=NULL;
               }
        } *head[MAXV];
        
        int h[MAXV],gap[MAXV],S,T;
        edge *d[MAXV];
        
        graph () {
               memset(head,0,sizeof(head));
        }
        
        void Add(int s,int t,int f) {
               edge *p=new(edge);
               p->t=t,p->f=f,p->next=head[s];
               head[s]=p;
        }
        void AddEdge(int s,int t,int f) {
               Add(s,t,f),Add(t,s,0);
               head[s]->pair=head[t],head[t]->pair=head[s];
        }
        
        int sap(int v,int flow) {
               if (v==T) return flow;
               int rec=0;
               for (edge *p=d[v];p;p=p->next) if (h[v]==h[p->t]+1&&p->f) {
                       int ret=sap(p->t,min(flow-rec,p->f));
                       p->f-=ret,p->pair->f+=ret,d[v]=p;
                       if ((rec+=ret)==flow) return flow;
               }
               if (!(--gap[h[v]])) h[S]=T;
               gap[++h[v]]++,d[v]=head[v];
               return rec;
        }
        
        int maxflow() {
               memset(h,0,sizeof(h));
               memset(gap,0,sizeof(gap));
               gap[S]=T;
               for (int i=0;i++<T;) d[i]=head[i];
               int flow=0;
               while (h[S]<T) flow+=sap(S,inf);
               return flow;
        }
} g;
 
const int dir[8][2]={{-1,2},{1,2},{-1,-2},{1,-2},{2,-1},{2,1},{-2,-1},{-2,1}};
 
int v[MAXN][MAXN],n,map[MAXN][MAXN],V=0,sum=0;
bool f[MAXN][MAXN];
 
void dfs(int x,int y,bool flag) {
        f[x][y]=false;
        if (flag) g.AddEdge(g.S,v[x][y],1); else g.AddEdge(v[x][y],g.T,1);
        for (int i=0;i<8;i++) {
               int X=x+dir[i][0],Y=y+dir[i][1];
               if (X>0&&X<=n&&Y>0&&Y<=n) {
                       if (!map[X][Y]) {
                               if (flag) g.AddEdge(v[x][y],v[X][Y],1);
                               if (f[X][Y])dfs(X,Y,flag^true);
                       }
               }
        }
}
 
void Init() {
        scanf("%d",&n);
        for (int i=0;i++<n;) {
               char s[MAXN];
               scanf("%s",&s);
               for (int j=0;j<n;j++) {
                       map[i][j+1]=s[j]=='0'?0:1;
                       if (!map[i][j+1]) v[i][j+1]=++V,sum++;
               }
        }
        g.S=++V;
        g.T=++V;
        memset(f,true,sizeof(f));
        for (int i=0;i++<n;) for (int j=0;j++<n;) {
               if (f[i][j]&&map[i][j]==0) {
                       dfs(i,j,true);
               } 
        }
}
 
int main() {
        Init();
        printf("%d\n",sum-g.maxflow());
        return 0;
}