hdu1401 Solitaire ——双向宽搜

This way

    更新一个较为简短的版本，我才知道bool也是一个字节的，所以如果使用bool存状态，然后mp后面加个[2]的话，还是char的两倍。bitset甚至更大。 通常我们存储是从"状态"这一说法出发，包括普通的bfs搜索迷宫问题，我们也是将所有位置看成状态，数位dp也是状态。这里的状态就是四个点的x,y坐标，每个八种情况，那么所有情况就是mp数组所存储的.
    这道题使用双向宽搜的理由：
首先考虑实际所有可能情况是8^8=2^24.有点危险嗷。
如果双向宽搜，那么由于题目里面给定最多8步，为了让时间复杂度最小，开头走4步，结尾反搜4步的情况是最优的。
一颗棋子走一步的情况有4种，4颗棋子走一步的情况是16种，四颗棋子走四步的情况是16^4=2^16种。从开头和结尾走是两种情况，所以最终复杂度为2^17.那也就优化了很多（应该是差不多对的吧这样算）

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N=8;
char mp[N][N][N][N][N][N][N][N];//四个棋子x,y的所有状态
char c[]={'0','1'};
struct node{//双向宽搜，f=0表示起点搜出去，1表示终点搜出去
    pii p[4];
    short step;
    bool f;
}s,e;
int xmov[]={1,0,-1,0};
int ymov[]={0,1,0,-1};
int cal(node x,int i){//计算当前点是否与另一个点重复，来决定是否是跳一格的情况
    for(int j=0;j<4;j++)
        if(j!=i && x.p[i]==x.p[j])
            return true;
    return false;
}
queue<node>Q;
int bfs(){
    while(!Q.empty()){
        node u=Q.front(),v;Q.pop();
        for(int i=0;i<4;i++){//枚举棋子
            for(int j=0;j<4;j++){//枚举方向
                v=u;
                v.p[i].fi+=xmov[j];
                v.p[i].se+=ymov[j];
                if(v.p[i].fi<0||v.p[i].fi>=N||v.p[i].se<0||v.p[i].se>=N)continue;//多个判断剪枝
                if(cal(v,i)){
                    v.p[i].fi+=xmov[j];
                    v.p[i].se+=ymov[j];
                }
                if(v.p[i].fi<0||v.p[i].fi>=N||v.p[i].se<0||v.p[i].se>=N||cal(v,i))continue;
                sort(v.p,v.p+4);
                if(mp[v.p[0].fi][v.p[0].se][v.p[1].fi][v.p[1].se][v.p[2].fi][v.p[2].se][v.p[3].fi][v.p[3].se]==c[v.f])continue;
                if(mp[v.p[0].fi][v.p[0].se][v.p[1].fi][v.p[1].se][v.p[2].fi][v.p[2].se][v.p[3].fi][v.p[3].se]!=0)return 1;
                mp[v.p[0].fi][v.p[0].se][v.p[1].fi][v.p[1].se][v.p[2].fi][v.p[2].se][v.p[3].fi][v.p[3].se]=c[v.f];
                v.step+=1;
                if(v.step<4)Q.push(v);
            }
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d%d",&s.p[0].fi,&s.p[0].se)!=EOF){
        while(!Q.empty())Q.pop();
        memset(mp,0,sizeof mp);
        //if(mp[0][0][0][0][0][0][0][0]=='0')printf("YYY\n");
        s.p[0].fi--,s.p[0].se--;
        for(int i=1;i<4;i++)scanf("%d%d",&s.p[i].fi,&s.p[i].se),s.p[i].fi--,s.p[i].se--;
        for(int i=0;i<4;i++)scanf("%d%d",&e.p[i].fi,&e.p[i].se),e.p[i].fi--,e.p[i].se--;
        s.f=0,e.f=1;
        sort(s.p,s.p+4);sort(e.p,e.p+4);//为了剪枝，将所有棋子看成相同的个体
        mp[s.p[0].fi][s.p[0].se][s.p[1].fi][s.p[1].se][s.p[2].fi][s.p[2].se][s.p[3].fi][s.p[3].se]=c[0];
        mp[e.p[0].fi][e.p[0].se][e.p[1].fi][e.p[1].se][e.p[2].fi][e.p[2].se][e.p[3].fi][e.p[3].se]=c[1];
        Q.push(s),Q.push(e);
        int flag=0;
        for(int i=0;i<4;i++)
            if(s.p[i]!=e.p[i])
                flag=1;
        if(flag==0||bfs())printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}