10349

This is a bipartite matching problem. This can be solved using Ford fulkerson algorithm for Max flow problem.

#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;

int gr[500][500];
int rgr[500][500];
string str[50];
int h,w;
int numOfantena;
int parent[500];
bool visited[500];
int src,targt;

bool bfs(int s, int t)
{
    memset(visited, 0, sizeof(visited));
    queue <int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    while (!q.empty())
    {
        int a = q.front();
        q.pop();

        for (int i=0; i<=targt; i++)
        {
            if (visited[i]==false && rgr[a][i] > 0)
            {
                q.push(i);
                parent[i] = a;
                visited[i] = true;
            }
        }
    }

    return (visited[t] == true);
}

int fordFulkerson(int s, int t)
{
    int u, v;

    for (u = 0; u <=targt; u++)
        for (v = 0; v <= targt; v++)
             rgr[u][v] = gr[u][v];


    int max_flow = 0;

	memset(parent, -1, sizeof(parent));
    while (bfs(s, t))
    {
        int path_flow = INT_MAX;
        for (v=t; v!=s; v=parent[v])
        {
            u = parent[v];
            path_flow = min(path_flow, rgr[u][v]);
        }

        for (v=t; v != s; v=parent[v])
        {
            u = parent[v];
            rgr[u][v] -= path_flow;
            rgr[v][u] += path_flow;
        }
        max_flow += path_flow;
    }

    return max_flow;
}


int main()
{
    int t;
	cin>>t;
	while(t--)
	{
		cin>>h>>w;
		numOfantena = 0;
		for(int i=0;i<h;i++)
		{
			cin>>str[i];
		}

		memset(gr,0,sizeof(gr));
		memset(rgr,0,sizeof(rgr));

		src = 0;
		targt = h*w+1;
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(str[i][j]=='*')
				{
					numOfantena++;

					if((i+j)%2)
					{
						gr[src][i*w+j+1]=1;

						if(i-1>=0 && str[i-1][j]=='*')
						{
							gr[i*w+j+1][(i-1)*w+j+1]=1;
						}
						if(i+1<h && str[i+1][j]=='*')
						{
							gr[i*w+j+1][(i+1)*w+j+1]=1;
						}
						if(j-1>=0 && str[i][j-1]=='*')
						{
							gr[i*w+j+1][i*w+j-1+1]=1;
						}
						if(j+1<w && str[i][j+1]=='*')
						{
							gr[i*w+j+1][i*w+j+1+1]=1;
						}
					}
					else
						gr[i*w+j+1][targt]=1;
				}
			}
		}

		int flow = fordFulkerson(src, targt);
		cout<<(numOfantena-2*flow)+flow<<"\n";
	}

    return 0;
}