C++14(g++5.4) 解法, 执行用时: 166ms, 内存消耗: 18792K, 提交时间: 2019-03-04 20:26:53

#include<bits/stdc++.h>
using namespace std;
int dp[1<<22];
int main(){
	char s[30];
	int n,m,ans=0;
	queue<int>q;
	memset(dp,-1,sizeof(dp));
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%s",s);
		int f=0;
		for(int j=0;j<m;j++)
			f+=(1<<j)*(s[j]-'0');
		if(dp[f]==-1){
			dp[f]=0;
			q.push(f);
		}
	} 
	while(!q.empty()){
		int u=q.front();
		q.pop();
		ans=max(ans,dp[u]);
		for(int i=0;i<m;i++){
			if(dp[u^(1<<i)]==-1){
				dp[u^(1<<i)]=dp[u]+1;
				q.push(u^(1<<i));
			}
		}
	}
	printf("%d\n",m-ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 167ms, 内存消耗: 10476K, 提交时间: 2020-02-27 12:52:41

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,i,now,j,d[2000001];
char s[1001];
queue<int>q;
int main()
{
	scanf("%d%d",&n,&m);
	memset(d,-1,sizeof(d));
	for(i=1;i<=n;i++)
	{
		scanf("%s",s);
		now=0;
		for(j=0;j<m;j++)
		now=now*2+s[j]-'0';
		q.push(now);
		d[now]=0;
	}
	while(q.size())
	{
		now=q.front();q.pop();
		ans=max(ans,d[now]);
		for(i=0;i<m;i++)
		if(d[now^(1<<i)]==-1)
		{
			d[now^(1<<i)]=d[now]+1;
			q.push(now^(1<<i));
		}
	}
	printf("%d",m-ans);
}