小W与气球

可以设f[i]为f[i] 行覆盖情况为 i 时列的覆盖情况
f[i]=f[i^lowbit]|a[g[lowbit]];
这里的lowbiw表示i&-i
个人评价：思考难度提高-
      代码难度普及-

#include<bits/stdc++.h>
using namespace std;
const int maxn=25,maxm=(1<<20)+5;
int T,n,m,cnt[maxm],a[maxn],f[maxm],g[maxm];
char s[maxn][maxn];
void init()
{
 for(int i=0;i<(1<<20);++i) 
  cnt[i]=cnt[i/2]+(i&1);
 for(int i=1;i<=20;++i) 
  g[1<<(i-1)]=i;
}
int main() {
 init();
 for(scanf("%d",&T);T--;) 
 {
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i) 
  {
   scanf("%s",s[i]+1);
   a[i]=0;
   for(int j=1;j<=m;++j) 
   {
    if(s[i][j]=='*') 
     a[i]|=1<<(j-1);
   }
  }
  f[0]=0;
  int msk=(1<<n)-1;
  for(int i=1;i<=msk;++i) 
  {
   int lowbit=i&-i;
   f[i]=f[i^lowbit]|a[g[lowbit]];
  }
  int ans=1<<30;
  for(int i=0;i<=msk;++i) 
  {
   ans=min(ans,max(cnt[f[i]],cnt[msk^i]));
  }
  printf("%d\n",ans);
 }
 return 0;
}

来源：zr