hdu题目2209 （BFS,存储状态麻烦点）

https://acm.hdu.edu.cn/showproblem.php?pid=2209

1.从第一个纸牌开始，将它的其他状态入队，

2.然后取队首元素，如果 是结果，则输出步数返回，否则重复1.

关键在于如何储存当前纸币的状态，一般字符串方法会TLE

#define N 1<<20 

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<queue>
using namespace std;

bool vis[N];
int len,flag;
struct state{
    int s;
    int setp;
};
void bfs(int s)
{
    queue<state> Q; 
    state p,k;
    p.s = s;p.setp = 0;
    
    Q.push(p);
    vis[s]=1;
    int q;
    while(!Q.empty()){
        
        p = Q.front(); Q.pop();
        int tmp = p.s;
        if(tmp ==0 ) {
            flag = 1;
            printf("%d\n",p.setp);return;
        }
        for(int i=1;i<=len;i++){
            if(i==1)    q = tmp^3; // 3二进制是11，最左边两个 
            else q = tmp^(7<<(i-2)); //7二进制是111； 翻转3个 
            
            q &= (1<<len)-1;  //最右边的多翻转了，再次翻转回来 
            
            if(!vis[q]){
                vis[q] = 1;
                k.s = q;
                k.setp = p.setp+1;
                Q.push(k);
            }
        }  
    } 
} 


int main()
{
    int s,i;
    char tmp[22];
    while(~scanf("%s",tmp)){
        len = strlen(tmp);
        s = 0;
        for(i=0;i<len;i++) 
            s = (s<<1)+tmp[i]-'0'; //将初始字符串转换成int型 
        
        flag = 0;
        memset(vis,0,sizeof(vis));
        bfs(s);
        if(!flag) puts("NO");
    }
    return 0; 
}