记录编号	369433	评测结果	AAAAAAAAAA
题目名称	[CodeChef MINESREV] 扫雷反转	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.062 s
提交时间	2017-02-09 13:57:17	内存使用	3.42 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
int T,n,m,cnt;
char s[110][110];
int fa[N],color[N],tp[N],next[N],match[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void unit(int x,int y){fa[find(x)]=find(y);}
queue<int> Q;
vector<int> E[N];
int lca(int x,int y){
	static int C=0;C++;
	for (;;swap(x,y))
	if (x){
		x=find(x);
		if (color[x]==C) return x;
		color[x]=C;
		x=next[match[x]];
	}
}
void group(int a,int p){
	while (a!=p){
		int b=match[a],c=next[b];
		if (find(c)!=p) next[c]=b;
		if (tp[a]!=1) tp[a]=1,Q.push(a);
		if (tp[b]!=1) tp[b]=1,Q.push(a);
		unit(a,b);unit(b,c);
		a=c;
	}
}
bool bfs(int s){
	while (!Q.empty()) Q.pop();
	for (int i=1;i<=cnt;i++) fa[i]=i,next[i]=tp[i]=0;
	tp[s]=1;Q.push(s);
	while (!Q.empty()){
		int x=Q.front();Q.pop();
		for (int i=E[x].size()-1;i>=0;i--){
			int y=E[x][i];
			if (tp[y]==2||find(x)==find(y)) continue;
			if (!match[y]){
				next[y]=x;
				for (int i=y;i;){
					int u=next[i],v=match[u];
					match[i]=u;match[u]=i;
					i=v;
				}
				return 1;
			}
			if (tp[y]==1){
				int p=lca(x,y);
				if (find(x)!=p) next[x]=y;
				if (find(y)!=p) next[y]=x;
				group(x,p);
				group(y,p);
			}
			else{
				next[y]=x;tp[y]=2;
				tp[match[y]]=1;
				Q.push(match[y]);
			}
		}
	}
	return 0;
}
const int fx[8]={1,1,1,0,0,-1,-1,-1},fy[8]={1,0,-1,1,-1,1,0,-1};
int vis[110][110];
void flood(int x,int y){
	if (vis[x][y]||s[x][y]!=1) return;
	vis[x][y]=cnt;
	for (int k=0;k<8;k++) flood(x+fx[k],y+fy[k]);
}
int main()
{
	freopen("MINESREV.in","r",stdin);
	freopen("MINESREV.out","w",stdout);
	scanf("%d",&T);
	while (T--){
		int ans=0;
		scanf("%d%d",&n,&m);
		for (int i=1;i<=cnt;i++)
			E[i].clear(),match[i]=0;
		cnt=0;
		for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
		for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			vis[i][j]=0;
			if (s[i][j]=='.'){
				s[i][j]=1;
				for (int k=0;k<8;k++){
					int x=i+fx[k],y=j+fy[k];
					if (x&&x<=n&&y&&y<=m&&s[x][y]=='*') s[i][j]='.';
				}
			}
			if (s[i][j]=='*') ans++;
		}
		for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			if (s[i][j]==1&&!vis[i][j])
				cnt++,ans++,flood(i,j);
			if (s[i][j]=='.'){
				ans++;
				for (int k=0;k<8;k++)
				if (s[i+fx[k]][j+fy[k]]==1){
					ans--;break;
				}
			}
		}
		for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		if (s[i][j]=='.'){
			for (int k=0;k<8;k++){
				int x=i+fx[k],y=j+fy[k],c=vis[x][y];
				if (x&&x<=n&&y&&y<=m&&s[x][y]==1){
					for (int l=0;l<8;l++){
						int X=i+fx[l],Y=j+fy[l],C=vis[X][Y];
						if (X&&X<=n&&Y&&Y<=m&&s[X][Y]==1&&c!=C)
							E[c].push_back(C),E[C].push_back(c);
					}
				}
			}
		}
		for (int i=1;i<=cnt;i++)
			if (!match[i]) ans-=bfs(i);
		printf("%d\n",ans);
	}
	return 0;
}