poj 2133 Cow Imposters

這個題目需要注意的是一定要操作，即初始串及時跟目標串相同，仍然需要操作。   比較簡單的搜索，應該很容易看出來，一次bfs搜出所有結果即可。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[20];
int n,m;
int goal;
int dp[70000],turn[111];
int que[70000];
bool text[70000];
void bfs()
{
    memset(text,0,sizeof(text));
    int front=1,end=0;
    for(int i=1;i<=m;i++)
    for(int j=1;j<=m;j++)
    {
        que[++end]=(turn[i]^turn[j]);
        text[turn[i]^turn[j]]=1;
        dp[turn[i]^turn[j]]=1;
    }
    while(front<=end)
    {
        int tmp=que[front++];
        for(int i=1;i<=m;i++)
        if(!text[turn[i]^tmp])
        {
            text[turn[i]^tmp]=1;
            dp[turn[i]^tmp]=dp[tmp]+1;
            que[++end]=(turn[i]^tmp);
        }
    }
}

int cal(int a,int b)
{
    int tmp=(a^b),ret=0;
    while(tmp)
    {
        ret+=(tmp&1);
        tmp/=2;
    }
    return ret;
}

int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(dp,50,sizeof(dp));
        scanf("%s",a+1);
        int sum=0;
        for(int i=n,tmp=1;i>=1;i--)
        {
            sum+=(a[i]-'0')*tmp;
            tmp*=2;
        }
        goal=sum;
        for(int i=1;i<=m;i++)
        {
            scanf("%s",a+1);
            sum=0;
            for(int j=n,tmp=1;j>=1;j--)
            {
                sum+=tmp*(a[j]-'0');
                tmp*=2;
            }
            turn[i]=sum;
        }
        bfs();
        int ans=11111111,id;
        for(int i=0;i<70000;i++)
        if(dp[i]<111111111)
        if(cal(i,goal)<ans)
        {
            ans=cal(i,goal);
            id=i;
        }
        else if(cal(i,goal)==ans)
        {
            if(dp[i]<dp[id])
            {
                id=i;
            }
        }
        cout<<dp[id]<<endl;
        int s[20],lon=0;
        while(id)
        {
            s[++lon]=id%2;
            id/=2;
        }
        for(int i=lon+1;i<=n;i++)
        printf("0");
        for(int i=lon;i>=1;i--)
        printf("%d",s[i]);
        printf("\n");
    }
    return 0;
}