相当于用1*2的板覆盖给定的h*w的格子里的点,求最少的板。
可以把格子相邻的分成两个集合,如下图,0为一个集合,1的为一个,也就是(行数+列数)为奇数的是一个集合,为偶数的为另一个集合。
1010101
0101010
1010101
两个集合分别代表男和女,能不能结婚,首先要看是不是异性,然后看是不是相邻的。所以就是用二分图匹配了。g[i][j]>0的表明i和j是相邻的。
找出最大的配对数,然后总共需要的板就是点的总数-配对的对数。
#include<cstdio> #include<cstring> #define N 500 int t,ans,h,w,n,m,u[N],link[N],g[N][N],b[45][15]; char c; bool find(int a) { for(int i=1; i<=n; i++) if(g[a][i]&&!u[i]) { u[i]=1; if(!link[i]||find(link[i])) { link[i]=a; return true; } } return false; } int main() { scanf("%d",&t); while(t--) { n=m=ans=0; memset(g,0,sizeof g); memset(b,0,sizeof b); memset(link,0,sizeof link); scanf("%d%d ",&h,&w); for(int i=1; i<=h; i++) { for(int j=1; j<=w; j++) if((c=getchar())=='*') if((i+j)&1) { b[i][j]=++n; g[b[i-1][j]][b[i][j]]=b[i-1][j]; g[b[i][j-1]][b[i][j]]=b[i][j-1]; } else { b[i][j]=++m; g[b[i][j]][b[i-1][j]]=b[i-1][j]; g[b[i][j]][b[i][j-1]]=b[i][j-1]; } getchar(); } for(int i=1; i<=m; i++) { memset(u,0,sizeof(u)); if(find(i)) ans++; } printf("%d ",n+m-ans); } return 0; }