搜索

BFS：

1。双向广搜

hdu 1401

题意：一个8 x 8的棋盘，上面有4颗棋子，棋子可以上下左右移动。给定一个初始状态和一个目标状态，问能否在8步之内到达。棋子移动有两种方式：
1.将一个棋子移动到一个空的相邻格子中。
2.将一个棋子跳过一个相邻的棋子到一个空的格子中去。
思路：
1.从初始状态开始移动，最多移动4步。
2.从目标状态开始移动，最多移动4步。
3.搜索1时，将每个走到的状态标记为 1 ，每个坐标输入是，我们可以改成是，也就是说只要3个二进制位就可以表示一个横坐标或者纵坐标，6个二进制位就可以存一个棋子的坐标，个二进制位就可以表示一个棋盘的状态，也就是一个型整数就可以存一个棋盘的状态（也就是说 值用就能存），注意在前要先排序，比如（2,3），（2,4），（5,6），（5,7）与（2,4），（5,6），（5,7），（2,3）虽然顺序不同，但都是同一个状态。
4.搜索2时，如果当前状态为 1 ，输出“YES"；如果状态 为 0 ，标记为 2；如果状态为 2 ，跳过（其实就是剪枝）。
code：

#include<bits/stdc++.h>
using namespace std;
int dis[4][2]={0,1,0,-1,1,0,-1,0};
map<int,int> flag;
struct zuobiao{
    int x,y;
    bool check(){
        if(x>=0 && x<8 && y>=0 && y<8) return false;
        return true;
    }
    bool operator<(const zuobiao&a)const{
        return x!=a.x?x<a.x:y<a.y;
    }
};
typedef struct Node{
    zuobiao pos[4];
    int step;
}node;
int Hash(zuobiao *a) {
    int t=0;
    sort(a,a+4);
    for (int i=0;i<4;i++) {
        t|=(a[i].x<<(6*i));
        t|=(a[i].y<<(6*i+3));
    }
    return t;
}
bool judge(int x,int y,zuobiao *a,int v){
    for (int k=0;k<4;k++) if (k!=v) {
        if (a[k].x==x && a[k].y==y) return false;
    }
    return true;
}
bool bfs(int kind,node a) {
    int t=Hash(a.pos);
    if(kind==2&&flag[t]==1) return true;
    flag[t]=kind;
    queue<node>q;
    q.push(a);
    while(!q.empty()){
        node u=q.front(); q.pop();
        if (u.step>=4) continue;
        for (int i=0;i<4;i++)
        for (int j=0;j<4;j++) {
            node v=u; v.step++;
            v.pos[i].x+=dis[j][0];
            v.pos[i].y+=dis[j][1];
            if (v.pos[i].check()) continue;
            if ( judge(v.pos[i].x, v.pos[i].y, u.pos, i) ) {
                t=Hash(v.pos);
                if(kind==1&&flag[t]!=1) {
                    flag[t]=1; q.push(v);
                }
                if(kind==2) {
                    if(flag[t]==1) return true;
                    else if(flag[t]!=2) {
                        flag[t]=2; q.push(v);
                    }
                }
            }
            else {
                v.pos[i].x+=dis[j][0];
                v.pos[i].y+=dis[j][1];
                if (v.pos[i].check() || !judge(v.pos[i].x, v.pos[i].y, u.pos, i)) continue;
                t=Hash(v.pos);
                if(kind==1&&flag[t]!=1) {
                    flag[t]=1; q.push(v);
                }
                if(kind==2) {
                    if(flag[t]==1) return true;
                    else if(flag[t]!=2) {
                        flag[t]=2; q.push(v);
                    }
                }
            }
        }
    }
    return false;
}
int main() {
    node s,e;
    while( ~scanf("%d%d",&s.pos[0].x,&s.pos[0].y) ) {
        --s.pos[0].x; --s.pos[0].y;
        for(int i=1;i<4;++i) {
            scanf("%d%d",&s.pos[i].x,&s.pos[i].y);
            --s.pos[i].x,--s.pos[i].y;
        }
        for(int i=0;i<4;++i) {
            scanf("%d%d",&e.pos[i].x,&e.pos[i].y);
            --e.pos[i].x,--e.pos[i].y;
        }
        s.step=0; e.step=0;
        bfs(1,s);
        printf("%s\n",bfs(2,e)?"YES":"NO");
        flag.clear();
    }
    return 0;
}