题意用1*2的木板覆盖矩阵中的‘#’，（木板要覆盖的只能是‘#’），问最多能用几个木板覆盖
将#抽象为二分图的点，一个木板就是一个匹配，注意最后结果要除以2
Sample Input
1 6 ...... .##... .##... ....#. ....## ......
Sample Output
Case 1: 3
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 1000000007 10 const int INF=0x3f3f3f3f; 11 const double eps=1e-5; 12 typedef long long ll; 13 #define cl(a) memset(a,0,sizeof(a)) 14 #define ts printf("***** "); 15 const int MAXN=1005; 16 int n,m,tt; 17 char s[MAXN][MAXN]; 18 int uN,vN;//u,v的数目，使用前面必须赋值 19 int g[MAXN][MAXN];//邻接矩阵 20 int linker[MAXN]; 21 bool used[MAXN]; 22 int num[MAXN][MAXN]; 23 bool dfs(int u) 24 { 25 for(int v=0;v<vN;v++) 26 if(g[u][v]&&!used[v]) 27 { 28 used[v]=true; 29 if(linker[v]==-1||dfs(linker[v])) 30 { 31 linker[v] = u; 32 return true; 33 } 34 } 35 return false; 36 } 37 int hungary() 38 { 39 int res=0; 40 memset(linker,-1,sizeof(linker)); 41 for(int u=0;u<uN;u++) 42 { 43 memset(used,false,sizeof(used)); 44 if(dfs(u))res++; 45 } 46 return res; 47 } 48 int main() 49 { 50 int i,j,k; 51 #ifndef ONLINE_JUDGE 52 freopen("1.in","r",stdin); 53 #endif 54 int ca=0; 55 scanf("%d",&tt); 56 while(tt--) 57 { 58 scanf("%d",&n); 59 cl(g); 60 int tot=0; 61 cl(num); 62 for(i=0;i<n;i++) 63 { 64 scanf("%s",&s[i]); 65 for(j=0;j<n;j++) 66 { 67 if(s[i][j]=='#') num[i][j]=tot++; 68 } 69 } 70 71 uN=vN=tot; 72 for(i=0;i<n;i++) 73 { 74 for(j=0;j<n;j++) 75 { 76 if(s[i][j]=='#') 77 { 78 if(s[i+1][j]=='#'&&i+1<n) g[num[i][j]][num[i+1][j]]=1; 79 if(s[i][j+1]=='#'&&j+1<n) g[num[i][j]][num[i][j+1]]=1; 80 if(s[i-1][j]=='#'&&i-1>=0) g[num[i][j]][num[i-1][j]]=1; 81 if(s[i][j-1]=='#'&&j-1>=0) g[num[i][j]][num[i][j-1]]=1; 82 } 83 } 84 } 85 ca++; 86 printf("Case %d: %d ",ca,hungary()/2); 87 } 88 }