这是一道比较经典的二分匹配,将格子按黑白标记后,再将含‘*’的格子按黑白分成两组,建边.最后的结果就是总的‘*’的个数-匹配数.

    [cpp]

    #include<iostream>

    #include<cstdio>

    #include<vector>

    using namespace std;

    vector<int>map[400];//按奇偶性建二分图

    int t,n,m;

    int match[400],fy[400],ln,rn;

    int map1[41][11];//原始图

    int dirt ={0,1,0,-1,1,0,-1,0};

    int path(int u)

    {

    for(int i=0,j;i<map[u].size();i++)

    {

    j=map[u][i];

    if(!fy[j])

    {

    fy[j]=1;

    if(match[j]==-1||path(match[j]))

    {

    match[j]=u;

    return 1;

    }

    }

    }

    return 0;

    }

    int main()

    {

    int i,j,x,y,ans;

    char tmp;

    scanf(“%d”,&t);

    while(t--)

    {

    scanf(“%d%d”,&n,&m);

    ln=rn=0;

    for(i=1;i<=n;i++)

    {

    getchar();

    for(j=1;j<=m;j++)

    {

    scanf(“%c”,&tmp);

    if(tmp=='*')