UVa 10349 - Antenna Placement Solution

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
int t,r,c,pt;
vector<vector<int> > a,b;
vector<int> match;
bitset<400> vis;
int aug(int u){
    if(vis[u])
        return 0;
    vis[u]=1;
    for(int i=0;i<b[u].size();i++){
        int v=b[u][i];
        if(!match[v]||aug(match[v])){
            match[u]=v;
            match[v]=u;
            return 1;
        }
    }
    return 0;
}
int main(){
    cin>>t;
    while(t--){
        cin>>r>>c;
        a.assign(r,vector<int>(c));
        pt=1;
        for(int i=0;i<r;i++){
            ws(cin);
            for(int j=0;j<c;j++){
                char c;
                cin>>c;
                if(c=='*')
                    a[i][j]=pt++;
            }
        }
        b.assign(pt,vector<int>());
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(a[i][j]){
                    if(i>0&&a[i-1][j])
                        b[a[i][j]].push_back(a[i-1][j]),b[a[i-1][j]].push_back(a[i][j]);
                    if(j>0&&a[i][j-1])
                        b[a[i][j]].push_back(a[i][j-1]),b[a[i][j-1]].push_back(a[i][j]);
                    if(i<r-1&&a[i+1][j])
                        b[a[i][j]].push_back(a[i+1][j]),b[a[i+1][j]].push_back(a[i][j]);
                    if(j<c-1&&a[i][j+1])
                        b[a[i][j]].push_back(a[i][j+1]),b[a[i][j+1]].push_back(a[i][j]);
                }
            }
        }
        int ans=0;
        match.assign(pt,0);
        for(int i=1;i<pt;i++){
            if(match[i])
                continue;
            vis.reset();
            ans+=aug(i);
        }
        cout<<pt-ans-1<<endl;
    }
}