Description
给定一个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)
求在装置互不攻击的情况下，最多可以放置多少个装置。
Input
第一行一个整数N，表示矩阵大小为N*N。接下来N行每一行一个长度N的01串，表示矩阵。
Output
一个整数，表示在装置互不攻击的情况下最多可以放置多少个装置。
Sample Input
3
010
000
100
Sample Output
4
HINT
100%数据 N<=200
这……这不是裸的二分图最大点独立集么……匈牙利水过……
/**************************************************************
Problem: 3175
User: geng4512
Language: C++
Result: Accepted
Time:840 ms
Memory:9240 kb
****************************************************************/
#include<cstdio>
#define MAXN 40005
#define MAXM 1000005
struct node { int v, nxt; }e[MAXM];
int n, ecnt, Adj[MAXN], cnt, dd[8][2] = {-1, -2, -1, 2, -2, -1, -2, 1, 1, 2, 1, -2, 2, 1, 2, -1}, c[MAXN], tag, vis[MAXN];
inline void Add(int u, int v) {
++ ecnt; e[ecnt].v = v; e[ecnt].nxt = Adj[u]; Adj[u] = ecnt;
}
char s[300][300];
int dfs(int u) {
vis[u] = tag;
for(int i = Adj[u]; i; i = e[i].nxt)
if(tag != vis[e[i].v]) {
vis[e[i].v] = tag;
if(!c[e[i].v] || dfs(c[e[i].v])) {
c[u] = e[i].v;
c[e[i].v] = u;
return 1;
}
}
return 0;
}
inline int Hungary() {
int ans = 0;
for(int i = 1; i < n*n; ++ i) tag = i, ans += dfs(i);
return ans;
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++ i)
scanf("%s", s[i]);
for(int i = 0; i < n; ++ i) {
for(int j = 0; j < n; ++ j) {
if(s[i][j]-'0') ++ cnt;
else if((i+j)&1){
for(int k = 0; k < 8; ++ k) {
int x = i + dd[k][0], y = j + dd[k][1];
if(x < 0 || x >= n || y < 0 || y >= n || s[x][y] == '1') continue;
Add(i*n+j, x*n+y);
}
}
}
}
int ans = n*n-Hungary()-cnt;
printf("%d\n", ans);
return 0;
}