BZOJ054_移动玩具_KEY

这道题我写IDA*写挂了，TLE+WA，只AC了两个点。
这道题标算BFS+状态压缩。
code：
/**************************************************************
    Problem: 1054
    User: yekehe
    Language: C++
    Result: Accepted
    Time:84 ms
    Memory:40864 kb
****************************************************************/
 
#include <bits/stdc++.h>
using namespace std;
 
int N,T;
 
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
 
int l[10000000],h,t;
int f[1<<17];
 
void BFS()
{
    memset(f,127,sizeof f);
    l[++t]=N;
    f[N]=0;
        while(h<t){
            int front=l[++h];
            if(front==T){printf("%d",f[front]);return ;}
                    for(int i=0;i<4;i++){
                        if((front&(1<<i))!=(front&(1<<i+4))){
                            int to=front;
                            to^=(1<<i)+(1<<i+4);
                            if(f[to]>f[front]+1)f[to]=f[front]+1,l[++t]=to;
                        }
                        if(i!=3 && (front&(1<<i))!=(front&(1<<i+1))){
                            int to=front;
                            to^=(1<<i)+(1<<i+1);
                            if(f[to]>f[front]+1)f[to]=f[front]+1,l[++t]=to;
                        }
                    }
                    for(int i=4;i<8;i++){
                        if((front&(1<<i))!=(front&(1<<i+4))){
                            int to=front;
                            to^=(1<<i)+(1<<i+4);
                            if(f[to]>f[front]+1)f[to]=f[front]+1,l[++t]=to;
                        }
                        if(i!=7 && (front&(1<<i))!=(front&(1<<i+1))){
                            int to=front;
                            to^=(1<<i)+(1<<i+1);
                            if(f[to]>f[front]+1)f[to]=f[front]+1,l[++t]=to;
                        }
                    }
                    for(int i=8;i<12;i++){
                        if((front&(1<<i))!=(front&(1<<i+4))){
                            int to=front;
                            to^=(1<<i)+(1<<i+4);
                            if(f[to]>f[front]+1)f[to]=f[front]+1,l[++t]=to;
                        }
                        if(i!=11 && (front&(1<<i))!=(front&(1<<i+1))){
                            int to=front;
                            to^=(1<<i)+(1<<i+1);
                            if(f[to]>f[front]+1)f[to]=f[front]+1,l[++t]=to;
                        }
                    }
                    for(int i=12;i<16;i++){
                        if(i!=15 && (front&(1<<i))!=(front&(1<<i+1))){
                            int to=front;
                            to^=(1<<i)+(1<<i+1);
                            if(f[to]>f[front]+1)f[to]=f[front]+1,l[++t]=to;
                        }
                    }
        }
}
 
int main()
{
    string S;
    for(int i=1;i<=4;i++){
        cin>>S;
        for(int j=1;j<=4;j++)N=(N<<1)+S[j-1]-'0';
    }//cin>>S;
    for(int i=1;i<=4;i++){
        cin>>S;
        for(int j=1;j<=4;j++)T=(T<<1)+S[j-1]-'0';
    }
    BFS();
    return 0;
}
BZOJ054_移动玩具_KEY

相关推荐
