出题人题解 | #消消乐#

原题解链接：https://ac.nowcoder.com/discuss/150007

暴力

#define _CRT_SECURE_NO_DEPRECATE
/************************
*创建时间：2018 09 14
*文件类型：源代码文件
*题目来源：原创题
*当前状态：已通过
*备忘录：最小点覆盖 标程
*作者：HtBest
************************/
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <bitset>
// #include <sys/wait.h>
// #include <sys/types.h>
// #include <unistd.h>
using namespace std;
#define MAXN 2002
int n,m,head[MAXN],to[MAXN],_edge,visY[MAXN],visX[MAXN],march[MAXN];
char map[MAXN][MAXN];
struct EDGE 
{
	int a,b,next;
	EDGE(int a=0,int b=0,int next=0):a(a),b(b),next(next){}
}edge[100001];
/* Variable explain:

*/
void adde(int a,int b)
{
	edge[++_edge]=EDGE(a,b,head[a]);
	head[a]=_edge;
	// printf("%d %d\n",a,b);
}
void read()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%s",map[i]+1);
		for(int j=1;j<=m;++j)
		{
			if(map[i][j]=='*')adde(i,j);
		}
	}
	return;
}
bool find(int a)
{
	visX[a]=true;
	for(int i=head[a];i;i=edge[i].next)
	{
		int b=edge[i].b;
		if(visY[b])continue;
		visY[b]=1;
		if(!to[b]||find(to[b]))
		{
			to[b]=a;
			return march[a]=true;
		}
	}
	return false;
}
void solve()
{
	int ans=0,ls1=0;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)visY[j]=0;
		ans+=find(i);
	}
	printf("%d\n",ans);
	for(int i=1;i<=m;++i)visY[i]=0;
	for(int i=1;i<=n;++i)visX[i]=0;
	for(int i=1;i<=n;++i)if(!march[i])find(i);
	for(int i=1;i<=n;++i)if(!visX[i])++ls1;
	printf("%d ",ls1);
	for(int i=1;i<=n;++i)if(!visX[i])printf("%d ",i);
	printf("\n%d ",ans-ls1);
	for(int i=1;i<=m;++i)if(visY[i])printf("%d ",i);puts("");
}
int main()
{
	read();
	solve();
	return 0;
}