View difference between Paste ID: ervimVJN and qGq5Crzk

 //WA
 #include <iostream>
 #include <cstdio>
 #include <vector>
 #include <cstring>
 #include <cmath>
 #include <map>
 #include <set>
 #include <algorithm>
 #include <queue>
 #include <stack>
 #include <sstream>
 #include <ctime>
 
 using namespace std;
 
 typedef pair < int, int >     pii;
 typedef long long int         i64;
 typedef vector < pii >        vpii;
 typedef pair < i64, i64 >     pi64;
 typedef vector < int >        vi;
 typedef vector < vi >         vvi;
 
 #define rep(i,a,b)            for(int i=(int)a; i<(int)b; ++i)
 #define rep_it(s,a,b)         for(s :: iterator it=a; it!= b; it++)
 #define mp                    make_pair
 #define pb                    push_back
 #define clr(v)                v.clear()
 #define mset(a,x)	      memset(a, x, sizeof a)
 #define all(v)                v.begin(), v.end()
 #define err                   1E-8
 #define inf                   (1<<29)
 #define MAX                   1000
 
-//#define inf_4                 0x04040404 //   67372036 ** 27
+
-//#define inf_8                 0x08080808 //  134744072 ** 28
+
-//#define inf_16                0x10101010 //  269488144 ** 29
+
-//#define inf_32                0x20202020 //  538976288 ** 30
+
-//#define inf_64                0x40404040 // 1077952576 ** 31
+
-//#define inf_127               0x7f7f7f7f // 2139062143 ** 31
+
 
 void augment(int u, int ed){
    if(u == S) f = ed;
    else if(p[u] != -1){
       augment(p[u], min(res[p[u]][u], ed));
       res[p[u]][u] -= f;
       res[u][p[u]] += f;
    }
 }
 
 int maxFlow(int N){
    mf = 0;
    int u;
    do{
       f = 0;
 
       p = vi(N, -1);
       vi dist(N, inf);
       queue < int > Q;
       Q.push(S);
       dist[S] = 0;
 
       while(!Q.empty()){
 	 u = Q.front(); Q.pop();
 	 if(u == T) break;
 	 rep(v,0,N) if(res[u][v] > 0 && dist[v]==inf)
 	    dist[v]=dist[u]+1, p[v]=u, Q.push(v);
       }
       augment(T, inf);
       mf += f;
    }while(f != 0);
 }
 
 #define can(_i,_j) (_i>=0 && _j>=0 && _i<R && _j<C)
 
 int main(){
    int nT, cont;
    bool op;
    int ir, ic, u, v;
    vpii ast;
    map < pii, int > mapa;
    //char str[21];
    string str;
    //scanf("%d\n", &nT);
    cin >> nT;
    while(nT--){
       cont = 1;
       clr(ast); clr(mapa);
       mset(taken, false); mset(res, 0);
 
       //scanf("%d%d\n", &R, &C);
       cin >> R >> C;
       rep(i,0,R){
 	 //scanf("%s\n", str);
 	 cin >> str;
 	 rep(j,0,C) if(str[j] == '*') ast.pb(mp(i,j)), mapa[(mp(i,j))] = cont++;
 	 rep(j,0,C) M[i][j]=str[j];
       }
       S = 0;
       T = cont;
 
       rep(i,0,ast.size()){
 	 ir = ast[i].first;
 	 ic = ast[i].second;
 	 if(!taken[ir][ic]){
 	    queue < pii > Q;
 	    M[ir][ic] = (ir + ic) % 2 == 0 ? 'A' : 'B';
 	    Q.push(mp(ir, ic));
 	    while(!Q.empty()){
 	       ir = Q.front().first;
 	       ic = Q.front().second;
 	       Q.pop();
 
 	       if(taken[ir][ic]) continue;
 
 	       op = (M[ir][ic] == 'A');
 	       taken[ir][ic] = true;
 	       u = mapa[mp(ir, ic)];
 
 	       if(op) res[S][u] = 1;
 	       else res[u][T] = 1;
 
 	       rep(m,0,4) if(can(ir + mR[m], ic + mC[m]) && M[ir + mR[m]][ic + mC[m]] == '*'){
 		  M[ir + mR[m]][ic + mC[m]] = op ? 'B' : 'A';
 		  Q.push(mp(ir + mR[m], ic + mC[m]));
 
 		  v = mapa[mp(ir + mR[m], ic + mC[m])];
 		  if(op) res[u][v] = 1;
 		  else res[v][u] = 1;
 	       }
 	    }
 	 }
       }
 
       //rep(i,0,R){rep(j,0,C) cout << M[i][j]; cout << endl;}
 
       maxFlow(T+1);
       //printf("%d\n", cont - 1 - mf);
       cout << (cont - 1 - mf) << endl;
    }
    return 0;
 }