显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=100,SIZEM=2000;
int N,M;
int pos=0;
int g[SIZEN][SIZEN];
int id[SIZEN][SIZEN]={0};
bool mp[SIZEN][SIZEN];
int dx[]={0,0,-1,1,-1,-1,1,1},dy[]={1,-1,0,0,-1,1,-1,1};
vector<int> S[SIZEM];
int cnt,click;
void read()
{
memset(g,0,sizeof(g));
memset(id,0,sizeof(id));
memset(mp,0,sizeof(mp));
scanf("%d%d",&N,&M);
char line[SIZEN];
for(int i=0;i<N;i++)
{
scanf("%s",line);
for(int j=0;j<M;j++)
{
if(line[j]=='*') g[i][j]=-1;
else g[i][j]=0;
}
}
}
bool on(int x,int y)
{
if(x<0||y<0) return 0;
if(x>=N||y>=M) return 0;
return 1;
}
void prepare()
{
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
{
if(g[i][j]!=-1)
{
for(int k=0;k<8;k++)
{
int ni=i+dx[k],nj=j+dy[k];
if(on(ni,nj)&&g[ni][nj]==-1) g[i][j]++;
}
}
}
}
void flood(int x,int y,int now)
{
if(id[x][y]||g[x][y]!=0) return;
id[x][y]=now;
for(int i=0;i<8;i++)
{
if(on(x+dx[i],y+dy[i])) flood(x+dx[i],y+dy[i],now);
}
}
void make_gragh()
{
for(int i=1;i<=cnt;i++) S[i].clear();
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
vector<int> tmp;
if(g[i][j]==-1) click++;
else if(g[i][j]!=0)
{
for(int k=0;k<8;k++)
{
int ni=i+dx[k],nj=j+dy[k];
if(on(ni,nj)&&id[ni][nj]!=0)
{
if(tmp.empty()||tmp[0]!=id[ni][nj]) tmp.push_back(id[ni][nj]);
}
}
if(tmp.size()==0) click++;
if(tmp.size()==2)
{
if(mp[tmp[0]][tmp[1]]) continue;
S[tmp[0]].push_back(tmp[1]);
S[tmp[1]].push_back(tmp[0]);
mp[tmp[0]][tmp[1]]=mp[tmp[1]][tmp[0]]=1;
}
}
}
}
}
int Q[SIZEM],siz,T=0;
int belong[SIZEM],mark[SIZEM],vis[SIZEM],match[SIZEN],next[SIZEN];
int findb(int x)
{
if(belong[x]==x) return x;
return belong[x]=findb(belong[x]);
}
void unit(int a,int b)
{
a=findb(a);
b=findb(b);
if(a!=b) belong[a]=b;
}
int LCA(int x,int y)
{
T++;
while(true)
{
if(x!=-1)
{
x=findb(x);
if(vis[x]==T) return x;
vis[x]=T;
if(match[x]!=-1) x=next[match[x]];
else x=-1;
}
swap(x,y);
}
}
void group(int x,int y)
{
while(x!=y)
{
int b=match[x],c=next[b];
if(findb(c)!=y) next[c]=b;
if(mark[b]==2) mark[Q[siz++]=b]=1;
if(mark[c]==2) mark[Q[siz++]=c]=1;
unit(x,b),unit(b,c);
x=c;
}
}
void bfs(int s)//带花树增广
{
for(int i=1;i<=cnt;i++) next[i]=-1,belong[i]=i,mark[i]=0,vis[i]=0;
mark[s]=1;Q[0]=s;siz=1;
for(int front=0;match[s]==-1&&front<siz;front++)
{
int x=Q[front];
for(int i=0;i<S[x].size();i++)
{
int v=S[x][i];
if(match[x]==v) continue;
if(findb(x)==findb(v)) continue;
if(mark[v]==2) continue;
if(mark[v]==1)
{
int r=LCA(x,v);
if(findb(x)!=r) next[x]=v;
if(findb(v)!=r) next[v]=x;
group(x,r);
group(v,r);
}
else if(match[v]==-1)
{
next[v]=x;
//if(pos==44) cout<<s<<endl;
for(int u=v;u!=-1;)
{
int y=next[u];
int mv=match[y];
match[u]=y;match[y]=u;
u=mv;
}
break;
}
else
{
next[v]=x;
Q[siz++]=match[v];
mark[match[v]]=1;
mark[v]=2;
}
}
}
}
void work()
{
prepare();
cnt=0;click=0;T=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
if(g[i][j]==0&&id[i][j]==0)
{
cnt++;
flood(i,j,cnt);
}
}
}
make_gragh();
int r1=0;
for(int i=1;i<=cnt;i++) match[i]=-1;
for(int i=1;i<=cnt;i++) if(match[i]==-1) bfs(i);
for(int i=1;i<=cnt;i++) if(match[i]!=-1) r1++;
int ans=cnt+click-(r1/2);
printf("%d\n",ans);
}
int main()
{
freopen("MINESREV.in","r",stdin);
freopen("MINESREV.out","w",stdout);
int t;
scanf("%d",&t);
while(t)
{
t--;
pos++;
read();
work();
}
return 0;
}
mikumikumi