HDU 4185 二分匹配 1*2方格个数

#include <iostream>  
#include <stdio.h>  
#include <string.h>  
#include <set>  
#include <queue>  
#include <algorithm>  
#include <cstdlib>  
#include <vector>  
#include <math.h>  
#define N 202  
#define M 201  
using namespace std;  
  
int n;  
int map[N][N];  
  
int lef[N*N];//lef[v]表示Y集的点v 当前连接的点    
bool T[N*N];     //T[u] 表示Y集 u 是否已连接x集  
vector<int>G[N*N]; //匹配边  G[X集].push_back(Y集)  注意G 初始化  
bool match(int x){ // x和Y集 匹配 返回x点是否匹配成功  
    for(int i=0; i<G[x].size(); i++)  
    {  
        int v = G[x][i];  
        if(!T[v])  
        {  
            T[v] = true;  
            if(lef[v] == -1 || match( lef[v] ))  
            {  
                lef[v] = x;  
                return true;  
            }  
        }  
    }  
    return false;  
}  
  
int solve(){  
  
    memset(lef, -1, sizeof(lef));  
    int ans = 0;  
    for(int i = 1; i<= n; i++)//X集匹配，X集点标号从 1-pn 匹配边是G[左点].size()     
        for(int j = 1; j<=n; j++){  
            memset(T, 0, sizeof(T));  
            if( match( i*M +j ) ) ans++;  
        }  
        return ans;  
}  
  
void pipei(int x1,int y1,int x2,int y2){  
    if(map[x2][y2] || map[x1][y1])  return ;  
    if(x1>n || x2>n || y1>n || y2>n)return ;  
    G[ x1*M + y1 ] .push_back( x2*M + y2);  
}  
void Have_map(){  
    int i,j;  
    for(i=1;i<=n;i++)  
        for(j=1;j<=n;j++)  
            G[i*M+j].clear();  
    for(i=1;i<=n;i++)  
        for(j=1;j<=n;j++)  
        {     
            pipei(i,j, i,  j+1);  
            pipei(i,j+1, i,j);  
  
            pipei(i,j, i+1,  j);  
            pipei(i+1, j, i, j);  
        }  
}  
char s[N];  
int main(){  
    int i, j, t, Cas = 1;   scanf("%d",&t);  
  
    while(t--){  
        memset(map,0,sizeof(map));  
        scanf("%d",&n);  
  
        for(i = 1; i <= n; i++)  
        {  
            scanf("%s",s);  
            for(j = 1; j <= n; j++)  
                if(s[j-1] == '.')  
                    map[i][j] = 1;  
        }  
  
        Have_map();  
        int ans = solve();  
        printf("Case %d: %d\n", Cas++, ans>>1);  
  
    }  
    return 0;  
}  
/* 
1 
6 
...... 
.##... 
.##... 
....#. 
....## 
...... 

*/