hdu 1401 Solitaire

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1401
题记：一道双向bfs的题，用vis记录棋子的位置，将开始的棋子bfs四步，结束的棋子bfs四步，如果有开始和结束棋子位置一样的情况输出YES,否则输出NO。

#include<bits/stdc++.h>
using namespace std;
char vis[8][8][8][8][8][8][8][8];//记录四个棋子的状态
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//上下左右

struct point{
    int x;
    int y;
};

bool cmp(point a,point b){
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

struct node{
    point p[4];//把四个棋子的位置都存进去
    int step;//记录步数
};

int judge(node &s,int i,int j,int flag){
    if(flag==1){
        if(s.step>=4)//超过四步就返回
            return 0;
        s.step++;
    }
    s.p[i].x+=dir[j][0];
    s.p[i].y+=dir[j][1];
    if(s.p[i].x >= 0&&s.p[i].x < 8 &&s.p[i].y >=0&&s.p[i].y<8){//判断是否出界
        int k;
        for(k=0;k<4;k++){
            if(i!=k){
                if(s.p[i].x== s.p[k].x&& s.p[i].y==s.p[k].y){//判断这个棋子的四个方向是否有棋子
                    if(flag==1)
                        return judge(s,i,j,0);//判断跳过相邻棋子之后还是否有棋子
                    else
                        return 0;
                }
            }
        }
        if(k>=4){//符合条件可以走
            sort(s.p,s.p+4,cmp);
            return 1;
        }
    }
    return 0;
}

void bfs(node s1,node s2){
    queue<node>q1,q2;
    node ss;
    q1.push(s1);//入列
    q2.push(s2);
    vis[s1.p[0].x][s1.p[0].y][s1.p[1].x][s1.p[1].y][s1.p[2].x][s1.p[2].y][s1.p[3].x][s1.p[3].y]='1';
    vis[s2.p[0].x][s2.p[0].y][s2.p[1].x][s2.p[1].y][s2.p[2].x][s2.p[2].y][s2.p[3].x][s2.p[3].y]='2';
    while(!q1.empty()||!q2.empty()){
        if(!q1.empty()){
            for(int i=0;i<4;i++){//i表示第i个棋子
                for(int j=0;j<4;j++){//j表示走的方向
                    ss=q1.front();
                    if(judge(ss,i,j,1)){
                        if(vis[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y]=='1')
                            continue;
                        if(vis[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y]=='2'){
                            cout<<"YES"<<endl;//开始棋子的状态和结束棋子的状态相同
                            return ;
                        }
                    q1.push(ss);
                    vis[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y]='1';
                    //在q1中搜索过要标记为1
                    }
                }
            }
            q1.pop();
        }
        if(!q2.empty()){
            for(int i=0;i<4;i++){//i表示第i个棋子
                for(int j=0;j<4;j++){//j表示走的方向
                    ss=q2.front();
                    if(judge(ss,i,j,1)){
                        if(vis[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y]=='2')
                            continue;
                        if(vis[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y]=='1'){
                            cout<<"YES"<<endl;//开始棋子的状态和结束棋子的状态相同
                            return ;
                        }
                    q2.push(ss);
                    vis[ss.p[0].x][ss.p[0].y][ss.p[1].x][ss.p[1].y][ss.p[2].x][ss.p[2].y][ss.p[3].x][ss.p[3].y]='2';
                    //在q2中搜索过要标记为2
                    }
                }
            }
            q2.pop();
        }
    }
    cout<<"NO"<<endl;//没有一种情况符合条件
}

int main(){
    int x,y;
    while(cin>>x>>y){
        node s1,s2;
        s1.p[0].x=x-1;
        s1.p[0].y=y-1;
        //bfs下标从0开始，所以所有的x和y都要减一
        for(int i=1;i<4;i++){
            cin>>x>>y;
            s1.p[i].x=x-1;
            s1.p[i].y=y-1;
        }
        for(int i=0;i<4;i++){
            cin>>x>>y;
            s2.p[i].x=x-1;
            s2.p[i].y=y-1;
        }
        s1.step=0;//初始化步数为0
        s2.step=0;
        sort(s1.p,s1.p+4,cmp);
        /*for(int i=0;i<4;i++)可以验证一下是否排序成功
            cout<<s1.p[i].x<<" "<<s1.p[i].y<<" ";
        */
        sort(s2.p,s2.p+4,cmp);
        memset(vis,0,sizeof(vis));//初始化
        bfs(s1,s2);
    }
    return 0;
}