Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 210

int p[MAXN][MAXN];

int mx[8] = {-1,-2,-2,-1,1,2,2,1};

int my[8] = {-2,-1,1,2,2,1,-1,-2};

int to(int i,int j){return (i - 1) * m + j;}

struct edge

{

	int to,nxt;

}e[MAXN * MAXN * 8];

int edgenum = 0;

int lin[MAXN * MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

bool v[MAXN * MAXN];

int match[MAXN * MAXN];

bool dfs(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!v[e[i].to])

		{

			v[e[i].to] = true;

			if(match[e[i].to] == -1 || dfs(match[e[i].to]))

			{

				match[e[i].to] = k;

				return true;

			}

		}

	}

	return false;

}

int main()

{

	scanf("%d%d",&n,&m);

	int tot = 0;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			scanf("%d",&p[i][j]);

			if(p[i][j] == 0)++tot;

		}

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			if(p[i][j] == 1)continue;

			if((i + j) % 2 == 0)continue;

			for(int k = 0;k < 8;++k)

			{

				int ni = i + mx[k],nj = j + my[k];

				if(ni <= n && ni >= 1 && nj <= m && nj >= 1 && p[ni][nj] == 0)

				{

					add(to(i,j),to(ni,nj));

				}

			}

		}

	}

	int ans = 0;

	memset(match,-1,sizeof(match)); 

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			if(p[i][j] == 1 || (i + j) % 2 == 0)continue;

			memset(v,0,sizeof(v));

			if(dfs(to(i,j)))++ans;

		}

	}

	cout << tot - ans << endl;

	return 0;

}