uva 1252 ×îÉÙ¿´¼¸Î»Êý×Ö ¾Í¿ÉÒÔ·Ö±æ³öËùÓеĶþ½øÖÆÊý×Ö

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int dp[3600][3600],d[200],n,m;
int dfs(int s1,int s2){
 if(dp[s1][s2]!=INF) return dp[s1][s2];
 int t=0;
 for(int i=0;i<n;i++){
  if((d[i]&s1)==s2)
  t++;
 }
 if(t<=1) return dp[s1][s2]=0;
 for(int i=0;i<m;i++){
  if(s1&(1<<i)) continue;
  dp[s1][s2]=min(dp[s1][s2],max(dfs(s1|(1<<i),s2|(1<<i)),dfs(s1|(1<<i),s2))+1);
 }
 return dp[s1][s2];
}
int main(){
 while(scanf("%d%d",&m,&n)==2 && (n+m)){
  for(int i=0;i<n;i++){
   int t=0;
   char s[20];
   scanf("%s",s);
   for(int j=0;j<m;j++){
    if(s[j]=='1')
    t|=(1<<j);
   }
   d[i]=t;
  }
  memset(dp,0x3f,sizeof(dp));
  printf("%d\n",dfs(0,0));
 }
}