学步园

小记：A了这题又长了记性了。定了个全局变量又定了一个相同变量名的局部变量，一直测试不对，想法是肯定是对的。最后想了好久，终于看到了，唉，,b了。

题解：这题，因为只有0和1两种状态，而且题目也说了只有不超过20位的长度，因此我们可以将这个串转换成一个整数值，而每种翻转而成的状态都是唯一的，因此这个值也是唯一的，这个就很好的解决了搜索中某个状态是否搜索过的问题了。不过也是利用空间换时间，看题目提交的情况，唉，大神们就是大神们，差距太大了。如果有看到本文的，有更好的解决方案的大神，给小弟支个招，教教咱。在此先谢过。 继续，有了保存状态的方法后，就直接对每一种状态中的每一位进行bfs，当状态值为0时即表示已搜到，就返回。记得对每一个状态进行标记是否已搜索。

代码奉上：

#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;
#define MAX 1<<20
#define N 50

char s1[N];
int visited[MAX],num[MAX];
int len;

int bfs(int x){
    queue<int>q;
    q.push(x);
    int i, now, next;
    while(!q.empty()){
        now = q.front();//取头
        q.pop();//头出队
        for (i = 1; i <= len; i++){
            if(i == 1)
                next = now^3;//最左翻转两个
            else
                next = now^(7<<(i-2));//中间翻转3个

            next &= (1<<len)-1;//最右的时候翻转了三个，消掉一个

            if(visited[next])continue;//是否已搜过

            visited[next] = 1;//标记为已搜
            num[next] = num[now] + 1;//最少次数加一
            if(next == 0)   return num[next];//是否搜到了
            q.push(next);//没有，则入队
        }
    }
    return -1;
}

int main()
{
    int i, a;
    while(scanf("%s",s1)!=EOF){
        len = strlen(s1);
        a = 0;
        for(i = 0;i < len;i++)
            a = (a<<1) + s1[i] -'0';
        if(a){
            memset(visited,0,sizeof(visited));
            memset(num,0,sizeof(num));
            a = bfs(a);
        }
        if(a == -1)
            printf("NO\n");
        else printf("%d\n",a);
    }
    return 0;
}