图中有三类点：水、浮冰、冰山

船与其他在同一横纵轴内的船无法同时存在除非被冰山隔开

船只能被放置在水中

求最多能放多少船

对于每块水域只有放或不放置船两种选择，因此很容易联想到最大二分匹配。由于任何在同一线上的水域只能放一艘船，可以视作一个整体。所以对于每块水域，横向和纵向有交点则连线。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 51, MAXM = MAXN*MAXN;
char mp[MAXN][MAXN], ap[MAXN][MAXN];
int visr[MAXN][MAXN], visc[MAXN][MAXN], cntr, cntc;
int n, m;
vector<int> vc[MAXM];
int mb[MAXM], vis[MAXM];
void init()
{
    memset(visc, 0, sizeof visc);
    memset(visr, 0, sizeof visr);
    cntr = cntc = 0;
    for (int i = 0; i< MAXM; ++i) vc[i].clear();
}
int dfs(int a)
{
    for (int i = 0, j = vc[a].size(); i<j ; ++i)
    {
        int v = vc[a][i];
        if (!vis[v])
        {
            vis[v] = 1;
            if (!mb[v] || dfs(mb[v]))
            {
                mb[v] = a;
                return 1;
            }
        }
    }
    return 0;
}
int hungary(int a)
{
    int cnt = 0;
    memset(mb, 0, sizeof mb);
    for (int i = 1; i<= a; ++i)
    {
        memset(vis, 0, sizeof vis);
        cnt += dfs(i);
    }
    return cnt;
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int t;
    scanf("%d", &t);
    while (t--)
    {
        init();
        scanf("%d%d", &n, &m);
        for (int i = 0; i< n; ++i)
            scanf("%s", mp[i]);
        for (int i = 0; i< n; ++i)
        {
            for (int j = 0; j< m; ++j)
            {
                if (mp[i][j] == '*' && !visr[i][j])
                {
                    ++cntr;
                    for (int k = j; k< m && mp[i][k]!='#'; ++k)
                    {
                        if (mp[i][k] == 'o') continue;
                        visr[i][k] = cntr;
                    }
                }
            }
        }
        cntc = cntr;
        for (int j = 0; j< m; ++j)
        {
            for (int i = 0; i< n; ++i)
            {
                if (mp[i][j] == '*' && !visc[i][j])
                {
                    ++cntc;
                    for (int k = i; k< n && mp[k][j]!='#'; ++k)
                    {
                        visc[k][j] = cntc;
                        if (visr[k][j])
                            vc[visr[k][j]].push_back(cntc);
                    }
                }
            }
        }
        printf("%d\n", hungary(cntr));
    }
    return 0;
}