记录

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,s,l,t,k,x,y,tx,ty,qwq,top=1,i,j,ans,u[1000000],v[1000000],w[1000000],first[1000000],nxt[1000000],second[1000000],sd[1000000],cnt[1000000],db[8][2]={{3,1},{3,-1},{-3,1},{-3,-1},{1,3},{1,-3},{-1,3},{-1,-3}};
bool a[300][300],book[300][300],kind[1000000];
queue<int>q;
int ls(int x,int y)
{
	return x*300+y;
}
void add(int a,int b,int c)
{
	top++;
	u[top]=a;
	v[top]=b;
	w[top]=c;
	nxt[top]=first[a];
	first[a]=top;
	top++;
	v[top]=a;
	u[top]=b;
	nxt[top]=first[b];
	first[b]=top;
}
void color(int x,int y,bool z)
{
	int k,tx,ty;
	for(k=0;k<8;k++)
	{
		tx=x+db[k][0];
		ty=y+db[k][1];
		if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]==false&&book[tx][ty]==false)
		{
			book[tx][ty]=true;
			kind[ls(tx,ty)]=z^1;
			color(tx,ty,z^1);
		}
	}
	return ;
}
int dfs(int x,int flow)
{
	if(x==t)
	{
		ans+=flow;
		return flow;
	}
	int sum=0,mi,i;
	for(i=second[x];i!=0;i=nxt[i])
	{
		second[x]=i;
		if(w[i]!=0&&sd[v[i]]+1==sd[x])
		{
			mi=dfs(v[i],min(w[i],flow-sum));
			if(mi!=0)
			{
				w[i]-=mi;
				w[i^1]+=mi;
				sum+=mi;
				if(sum==flow)
					return sum;
			}
		}
	}
	cnt[sd[x]]--;
	if(cnt[sd[x]]==0)
		sd[s]=qwq+1;
	sd[x]++;
	cnt[sd[x]]++;
	return sum;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	qwq=n*m;
	for(;k>=1;k--)
	{
		scanf("%d%d",&x,&y);
		qwq-=(!a[x][y]);
		a[x][y]=true;
	}
//	cout<<qwq<<endl;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(a[i][j]==false)
			{
				for(k=0;k<8;k++)
				{
					tx=i+db[k][0];
					ty=j+db[k][1];
					if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&a[tx][ty]==false)
						add(ls(i,j),ls(tx,ty),1);
				}
			}
		}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(a[i][j]==true)
				continue;
			if(book[i][j]==true)
				continue;
			book[i][j]=true;
			kind[ls(i,j)]=false;
			color(i,j,false);
		}
	s=100000;
	t=200000;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(kind[ls(i,j)])
				add(ls(i,j),t,1);
			else
				add(s,ls(i,j),1);
		}
	memset(sd,-1,sizeof(sd));
	cnt[0]=1;
	sd[t]=0;
	q.push(t);
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(i=first[x];i!=0;i=nxt[i])
		{
			if(sd[v[i]]!=-1)
				continue;
			sd[v[i]]=sd[x]+1;
			cnt[sd[v[i]]]++;
			q.push(v[i]);
		}
	}
	while(sd[s]<qwq)
	{
		memcpy(second,first,sizeof(first));
		dfs(s,1e9+7);
	}
	printf("%d",qwq-ans);
}