muddy.cpp

#include<bits/stdc++.h>
using namespace std;

#define MAXV 1300
#define MAXF 60

int T, r, c, i, j, flow,H,W;
char m[MAXF][MAXF];
bool vis[MAXV];
int res[MAXV][MAXV], p[MAXV];
int wi[MAXF][MAXF], hi[MAXF][MAXF];

bool augment(int x) {

    if (vis[x]) return false;

    vis[x] = true;
    for (int i = 1; i <= H; i++)
      if (res[x][i] && (!p[i] || augment(p[i]))) {
        p[i] = x;
        return true;
      }

    return false;
  }

int main() {
  scanf("%d", &T);
  
  while(T--) {
    flow = 0, H = 0, W = 0;
    memset(res, 0, sizeof(res));
    memset(p, 0, sizeof(p));

    scanf("%d %d", &r, &c);
    for (i = 0; i < r; i++)
      scanf( "%s", &m[i] );

    for (i = 0; i < r; i++)
      for (j = 0; j < c; j++)
        if (m[i][j] == '*') {

          if (i == 0 || m[i - 1][j] == '.') wi[i][j] = ++W;
          else wi[i][j] = wi[i - 1][j];

          if (j == 0 || m[i][j - 1] == '.') hi[i][j] = ++H;
          else hi[i][j] = hi[i][j - 1];

          res[wi[i][j]][hi[i][j]] = 1;
        }

    for (i = 1; i <= W; i++) {
      memset(vis, false, sizeof(vis));
      if (augment(i)) flow++;
    }

    printf( "%d\n", flow );
  }

  return 0;
}