POJ1753 搜索

#include "cstdio"
#include "algorithm"
#include "queue"
#include "cmath"
#include "cstring"

#define  inf 0x3f3f3f
using namespace std;
int g[16];
char s[4][4];
bool use[65536];
typedef  struct {
    int st,s;
}N;
int bfs(int s){
    queue<N>q;
    N no,ne;
    memset(use, false, sizeof(use));
    no.st=s,no.s=0;
    q.push(no);
    use[s]=true;
    while (q.size()){
        no=q.front();
        q.pop();
        if(no.st==0||no.st==65535){
            return no.s;
        }
        for(int i=0;i<16;i++){
            ne.st=no.st^g[i];
            ne.s=no.s+1;
            if(use[ne.st]){
                continue;
            }
            if(ne.st==0||ne.st==65535){
                return  ne.s;
            }
            use[ne.st]= true;
            q.push(ne);
        }
    }
    return -1;
}
int main()
{
    memset(g,0, sizeof(g));
    for(int i=0;i<16;i++){／／存储16个翻子操作
        int n=15-i;
        g[i]=pow(2,n);
        if(n+1<=n/4*4+3){
            g[i]+=pow(2,n+1);
        }
        if(n-1>=n/4*4){
            g[i]+=pow(2,n-1);
        }
        if(n+4<=15){
            g[i]+=pow(2,n+4);
        }
        if(n-4>=0){
            g[i]+=pow(2,n-4);
        }
    }
    while (scanf("%s",s[0])!=EOF){
        for(int i=1;i<4;i++){
            scanf("%s",s[i]);
        }
        int st=0;
        for(int i=0;i<4;i++){／／将初始状态转为数字
            for(int j=0;j<4;j++){
                st<<=1;
                if(s[i][j]==‘b‘){
                    st++;
                }
            }
        }
        int x=bfs(st);
        if(x==-1){
            printf("Impossible\n");
        }else{
            printf("%d\n",x);
        }
    }
    return 0;
}