Description
jswf夺冠后
cc: tql
gj: tggl
mz：tlrxml
frz: bksjs
wjjj: whnzmqa
......
js: ??? 
js: nmflb

————节选自某次mz语等级测试

mz语等级测试即将到来。然而mz语十分难，用词灵活多变，导致作弊人数众多。而防止考生作弊的一个有效的途径是让考生之间保持一定的距离。

某考场有R（行）*C（列）个座位，坐在(r, c)的考生可能会看到(r,c-1)、(r,c+1)、(r-1,c-1)、(r-1,c+1)（即左、右、左前、右前）4个位置的考生的答案。

为了防止这种情况发生，就要保证一个考生周围的这4个位置中无其他考生。

而由于这个考场年久失修，有一些座位已经损坏，是无法使用的。

现在，fls想知道，在保证无人能看到别人答案的前提下，这个考场最多能安排多少名考生？

Input
多组数据

第一行有一个整数T(T<=30)，代表数据组数。

对每组数据，第一行有两个整数R、C(1 <= R, C <= 50)，表示考场规模。

接下来R行，每行有一个长度为C的字符串，描述考场内每个位置。'.'表示该位置可用，'x'则表示已损坏。

Output
对每组数据，输出该考场内最多能安排的考生数。

Sample Input
1
2 3
...
.x.
Sample Output
4

相隔两列的人是看不见对方的。所以把有冲突的座位连边即为二分图。

任意两个冲突的位置只能有一个地方坐人，即任意点只能有一条边相连。边数就是能坐下的人。转化为了最小边覆盖问题。

答案就是 点数-最大匹配数

注意link vis这些变量名有可能会与STL冲突

#include<vector>
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<string> 
using namespace std;
int dx[]={-1, 0, 1,-1,0,1};
int dy[]={-1,-1,-1, 1,1,1};
char tsr[55][55];
vector<int> G[3025];
int id[55][55];
int visa[3025]={0};
int linka[3025]={0};
int r,c;
int lig(int x,int y)
{
	return x<=r&&x>=0&&y<=c&&y>=0;
}
int hung(int x)
{
	int v;
	for(int i=0;i<G[x].size();i++)
	{
		v=G[x][i];
		if(visa[v]) continue;
		visa[v]=1;
		if(linka[v]==0||hung(linka[v]))
		{
			linka[v]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(linka,0,sizeof(linka));
		memset(id,0,sizeof(id));
		int cnt1=0,cnt2=0;
		scanf("%d%d",&r,&c);
		for(int i=1;i<=r;i++) scanf("%s",tsr[i]+1);
		for(int i=1;i<=r;i++)
		{
			for(int j=1;j<=c;j++)
			{
				if(tsr[i][j]!='.') continue;
				if(j&1) id[i][j]=++cnt1;
				else id[i][j]=++cnt2;
			}
		}
		for(int i=1;i<=cnt1;i++) G[i].clear();
		for(int i=1;i<=r;i++)
		{
			for(int j=1;j<=c;j+=2)
			{
				if(tsr[i][j]!='.') continue;
				for(int k=0;k<6;k++)
				{
					int x=i+dx[k],y=j+dy[k];
					if(tsr[x][y]=='.' && lig(x,y))
					{
						G[id[i][j]].push_back(id[x][y]);
					}
				}
			}
		}
		int ans=0;
		for(int i=1;i<=cnt1;i++)
		{
			memset(visa,0,sizeof(visa));
			ans+=hung(i);
		}
		printf("%d\n",cnt1+cnt2-ans);
	}
}