POJ 2133 暴搜

题意：



思路：

按照题意暴搜

注意 如果目标串==给的串 答案是2

//By SiriurRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int n,k,goal,a[1005],head,tail,q[1000000],vis[1<<16],minn[17],rec[17];

char p;

int main(){

    memset(minn,0x3f,sizeof(minn));

    scanf("%d%d",&k,&n),getchar();

    for(int i=1;i<=k;i++)p=getchar(),goal=goal*2+p-'0';

    for(int i=1;i<=n;i++){

        getchar();

        for(int j=1;j<=k;j++)

            a[i]=a[i]*2+getchar()-'0';

        q[tail++]=a[i];

    }

    while(head<tail){

        int t=q[head++];

        for(int i=1;i<=n;i++)

            if(!vis[t^a[i]])

                vis[t^a[i]]=vis[t]+1,q[tail++]=t^a[i];

    }

    for(int i=0;i<(1<<k);i++){

        if(!vis[i])continue;

        int jy=i^goal,temp=0;

        for(int j=0;j<k;j++)if(jy&(1<<j))temp++;

        if(minn[temp]>vis[i])minn[temp]=vis[i],rec[temp]=i;

        else if(minn[temp]==vis[i])rec[temp]=min(rec[temp],i);

    }

    for(int i=0;i<=k;i++)

        if(minn[i]<=0x3ffffff){

            printf("%d\n",minn[i]);

            for(int j=k-1;j>=0;j--)

                printf("%d",rec[i]&(1<<j)?1:0);

            return 0;

        }

}