http://172.20.6.3/Problem_Show.asp?id=1383
找能到达某个状态的最小操作数，然后把所有状态扫一遍即可，要额外判定一下起始就有的状态（如果起始里没有0那么这些状态应该起始是2（异或同一个数）），写博客的时候才意识到我的这个代码是有问题的，最开始应该把所有的状态都判定一边啊…不想改了就这样好了，OJ数据真水
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const int maxn=1<<17; 9 int n,m; 10 char ch[110][20]={}; 11 int a[110]={}; 12 int f[maxn]={}; 13 int wtf1=0,wtf2=0; 14 queue<int>q; 15 int main(){ 16 scanf("%d%d",&n,&m); 17 for(int i=0;i<=m;i++){ 18 scanf("%s",&ch[i]); 19 int z=1; 20 for(int j=n-1;j>=0;j--){ 21 a[i]+=z*(int)(ch[i][j]-'0'); 22 z*=2; 23 } 24 if(i!=0&&a[i]==a[0]){ 25 m--;i--;wtf1=1;wtf2=a[i]; 26 } 27 } 28 memset(f,63,sizeof(f));int ww=f[1]; 29 for(int i=1;i<=m;i++)f[a[i]]=0,q.push(a[i]); 30 while(!q.empty()){ 31 int x=q.front();q.pop(); 32 for(int i=1;i<=m;i++){ 33 int y=x^a[i]; 34 if(f[y]>f[x]+1){ 35 f[y]=f[x]+1; 36 q.push(x^a[i]); 37 } 38 } 39 }int ma=(1<<n)-1,x1,t,x; 40 int id=ma,ans=ma; 41 for(int i=0;i<=ma;i++){ 42 if(f[i]==ww)continue; 43 x1=i^a[0],t=0; 44 while(x1){ 45 x1-=(x1&(-x1)); 46 t++; 47 } 48 if(t<ans||(t==ans&&f[i]<id)){ 49 ans=t;x=i;id=f[i]; 50 } 51 } 52 if(wtf1&&(id>2||ans>0)){id=2;x=a[0];} 53 printf("%d ",id); 54 int z; 55 for(int i=n-1;i>=0;i--){ 56 z=1<<i; 57 printf("%d",x/z); 58 x=x%z; 59 } 60 return 0; 61 }