Hiding Gold

You are given a 2D board where in some cells there are gold. You want to fill the board with 2 x 1 dominoes such that all gold are covered. You may use the dominoes vertically or horizontally and the dominoes may overlap. All you have to do is to cover the gold with least number of dominoes.

In the picture, the golden cells denote that the cells contain gold, and the blue ones denote the 2 x 1 dominoes. The dominoes may overlap, as we already said, as shown in the picture. In reality the dominoes will cover the full 2 x 1 cells; we showed small dominoes just to show how to cover the gold with 11 dominoes.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a row containing two integers m (1 ≤ m ≤ 20) and n (1 ≤ n ≤ 20) and m * n > 1. Here m represents the number of rows, and n represents the number of columns. Then there will be m lines, each containing n characters from the set ['*','o']. A '*' character symbolizes the cells which contains a gold, whereas an 'o' character represents empty cells.

Output

For each case print the case number and the minimum number of dominoes necessary to cover all gold ('*' entries) in the given board.

Sample Input

2

5 8

oo**oooo

*oo*ooo*

******oo

*o*oo*oo

******oo

3 4

**oo

**oo

*oo*

Sample Output

Case 1: 11

Case 2: 4

题意描述：

在n*m的地图中‘*’代表着黄金，现在要用1*2或2*1的骨牌去遮盖所有的黄金问最少需要多少个骨牌（骨牌可以重叠）

解题思路：

在网上看的题解，相当于将n*m地图上的每个点都编了号码，0~n*m-1；相邻的两个黄金是有关系的，定义一个（n*m）*（n*m）的二维数组，将有关系的黄金对应的编号位置存储为1，统计出所有的黄金数，将有关系的利用匈利亚算法找出最大匹配，因为存储时存储为双向图，所以最大匹配数为匈牙利算法求得的最大匹配数/2，最小路径覆盖数=顶点数 - 最大匹配数（骨牌的最小数=黄金数-最大匹配数）

#include<stdio.h>
#include<string.h>
char e[30][30];
int map[500][500];
int v[30][30],match[500],book[500];
int n,m;
int next[4][2]={0,1,1,0,-1,0,0,-1};
void dfsmap(int x,int y)
{
	int k,tx,ty;
	for(k=0;k<=3;k++)
	{
		tx=x+next[k][0];
		ty=y+next[k][1];
		if(tx>=0&&tx<n&&ty>=0&&ty<m)
			if(e[tx][ty]=='*')
				map[x*m+y][tx*m+ty]=1;//存储关系 
	}
}
int dfs(int u)
{
	int i;
	for(i=0;i<n*m;i++)
	{
		if(book[i]==0&&map[u][i]==1)
		{
			book[i]=1;
			if(match[i]==-1||dfs(match[i]))
			{
				match[i]=u;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int i,j,t,sum,ans,cut;
	while(scanf("%d",&t)!=EOF)
	{
		cut=0;
		while(t--)
		{
			cut++;
			scanf("%d%d",&n,&m);
			for(i=0;i<n;i++)
				scanf("%s",e[i]);
			memset(map,0,sizeof(map));
			memset(match,-1,sizeof(match));//因0也是定点，所以不可再制0，用-1 
			sum=0;
			ans=0;
			for(i=0;i<n;i++)
				for(j=0;j<m;j++)
				{
					if(e[i][j]=='*')
					{
						sum++;
						dfsmap(i,j);
					}
				}
			for(i=0;i<n*m;i++)
			{
				memset(book,0,sizeof(book));
				if(dfs(i))
					ans++;
			}
			printf("Case %d: %d\n",cut,sum-ans/2);
		}
	}
	return 0;
}