Hdu1401 Solitaire

题意

有一个8x8的棋盘，上面有4个棋子，棋子可以这样移动：1.移动到相邻空位置 2.跳过一个棋子到其前面，具体看图。然后给你两个棋盘到布局，问布局1是否可以在8步之内移动成布局2的样子？

分析

可以想到这是一个最短路问题，每一个棋盘布局就是一种状态，从初始状态移动到目标状态就是一个求最短路的过程。
这题由于给了初始状态和目标状态，所以很容易就想到是双向BFS算法写的话时间复杂度更低，保存的中间状态就更少，所以内存也会更少。

如何存储状态

显然我们可以使用string来存储棋盘，空的位置是0，有棋子的位置是1，然后串起来就可以hash了，但是此处可以看到是8x8=64个位置的棋盘，可以联想到用longlong来存棋盘，每一个位置用一个二进制位来存，这样不同布局，其long long值就不同。为何不选用string是因为，对string哈希需要一定时间，在unorder_map中，而longlong可以直接存取。

AC代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
int dir[4][2] = {-1,0,1,0,0,1,0,-1};
int dir2[4][2] = {-2,0,2,0,0,2,0,-2};
struct node{
    ull hs;//哈希值
    int st[8][8];//棋盘布局
    int pos[4][2];//棋子位置
}st1,st2;

ull Hash(node &no){ //哈希函数，将棋盘转换成unsigned long long
    ull hs = 0;
    for(int i = 0;i<8;i++){
        for(int j = 0;j<8;j++){
            hs = hs<<1| no.st[i][j];
        }
    }
    return hs;
}

int ex(queue<node> &q,unordered_map<ull,int> &mp1,unordered_map<ull,int> &mp2){
    node cur = q.front();q.pop();
    for(int i = 0;i<4;i++){
        int x =  cur.pos[i][0],y = cur.pos[i][1];
        for(int j = 0;j<4;j++){
            int dx = x+dir[j][0];
            int dy = y+dir[j][1];
            if(dx>=0 && dx<8 && dy>=0 && dy<8 && cur.st[dx][dy] == 0){ //尝试距离为1的位置
                node ne = cur;
                ne.st[x][y] = 0;
                ne.st[dx][dy] = 1;
                ne.pos[i][0] = dx,ne.pos[i][1] = dy;
                ne.hs = Hash(ne);
                if(!mp1.count(ne.hs)){
                    mp1[ne.hs] = mp1[cur.hs]+1;
                    q.push(ne);
                    if(mp2.count(ne.hs))return mp1[ne.hs]+mp2[ne.hs];
                }
            }else if(dx>=0 && dx<8 && dy>=0 && dy<8 && cur.st[dx][dy] == 1){
                dx = x+dir2[j][0];
                dy = y+dir2[j][1];
                if(dx>=0 && dx<8 && dy>=0 && dy<8 && cur.st[dx][dy] == 0){//尝试距离为2的位置
                    node ne = cur;
                    ne.st[x][y] = 0;
                    ne.st[dx][dy] = 1;
                    ne.pos[i][0] = dx,ne.pos[i][1] = dy;
                    ne.hs = Hash(ne);
                    if(!mp1.count(ne.hs)){
                        mp1[ne.hs] = mp1[cur.hs]+1;
                        q.push(ne);
                        if(mp2.count(ne.hs)) return mp1[ne.hs]+mp2[ne.hs];
                    }
                }
            }
        }
    }
    return -1;
}
int bfs(){
    unordered_map<ull,int> dis1,dis2;
    queue<node> q1,q2;
    q1.push(st1);q2.push(st2);
    dis1[st1.hs] = 0;dis2[st2.hs] = 0;

    while(q1.size() && q2.size()){
        if(dis1[q1.front().hs] + dis2[q2.front().hs]>8) return -1;
        int res;
        if(q1.size() <= q2.size()) res = ex(q1,dis1,dis2);
        else res = ex(q2,dis2,dis1);
        if(res!= -1 && res<=8) return res;
        if(res>8) return -1;
    }
    return -1;
}

int main(){
    int x,y;
    while(~scanf("%d %d",&x,&y)){
        x--;y--; //减一，是因为我想从下标0开始
        memset(st1.st,0,sizeof(st1.st));
        memset(st2.st,0,sizeof(st2.st));
        st1.st[x][y] = 1;
        st1.pos[0][0] = x,st1.pos[0][1] = y; //存储棋子的位置
        for(int i = 1;i<=3;i++){
            scanf("%d %d",&x,&y);x--;y--;
            st1.st[x][y] = 1;
            st1.pos[i][0] = x,st1.pos[i][1] = y;
        }
        for(int i = 0;i<4;i++){
            scanf("%d %d",&x,&y);x--;y--;
            st2.st[x][y] = 1;
            st2.pos[i][0] = x,st2.pos[i][1] = y;
        }
        st1.hs = Hash(st1);
        st2.hs = Hash(st2);
        if(st1.hs == st2.hs)
            puts("YES");
        else{
            int res = bfs();
            if(res == -1) puts("NO");
            else {
                puts("YES");
            }
        }
    }
    return 0;
}