hdu6171 Admiral

题意：给你一个如图形状21个元素的排列，只能够通过0元素跟其上下相邻的元素进行交换，问是否可以在20步内转换成目标排列，如果可以输出最小步数，否则输出too difficult

这是目标排列，给定的初始排列可能不同

分析

首先可以看出这是一个求最短路的题，我们可以把元素的排列看成是一种状态，他可以经过若干次状态转移到达目标状态，这就是一个最短路问题了。

尝试使用普通BFS

0元素可以向四个方向移动，上左，上，下，下右，极端情况走到21步(也就是too difficult)，一共有4^21的复杂度，1e12的数量级了，普通bfs必定会超时。

尝试使用双向BFS

让初始排列和目标排列一起扩展，极端情况，双方各扩展10步，也就是两个4^10,2e6的数量级，然后在双方扩展的过程中，看有没有交集。如果有交集就判断是否是20步以内，如果两个队头状态的步数相加已经超过20步了，也要结束循环。

状态怎么存储

如果我们把这个排列数组存下来，可见非常消耗内存，可以通过哈希的方式存储，可以将排列转换成字符串，也可以将排列用自建哈希函数，因为一个只有21个数，每个数是0～5，只占用3个二进制位，一共需要占用63个二进制位，而longlong有64个二进制位，所以其状态可以用一个longlong来存储。

双向BFS+string存储

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;
const int maxn = 1e6+10;
typedef pair<int,int> pii;
int T,sx,sy;
string a,b;
unordered_map<string,int> disa,disb;
unordered_map<string,pii> posa,posb;
queue<string> qa,qb;

int extentA(){
    string cur = qa.front();qa.pop();
    int d = disa[cur];
    pii p = posa[cur];
    int x = p.first,y = p.second;
    int nx = -1,ny = -1;
    for(int i = 0;i<4;i++){
        if(i == 0) nx = x-1,ny = y;
        if(i == 1) nx = x-1,ny = y-1;
        if(i == 2) nx = x+1,ny = y;
        if(i == 3) nx = x+1,ny = y+1;
        if(nx>=1 && nx<=6 && ny>=1 && ny<=nx){
            swap(cur[x*(x-1)/2+y],cur[nx*(nx-1)/2+ny]);
            if(!disa[cur]){
                qa.push(cur);
                disa[cur] = d+1;
                posa[cur] = {nx,ny};
                if(disb.count(cur)) return disa[cur] + disb[cur];
            }
            swap(cur[x*(x-1)/2+y],cur[nx*(nx-1)/2+ny]);
        }
    }

    return -1;
}
int bfs(){
    disa.clear();disb.clear();
    posa.clear();posb.clear();
    while(qa.size()) qa.pop();
    while(qb.size()) qb.pop();
    qa.push(a);qb.push(b);
    disa[a] = 0,disb[b] = 0;
    posa[a] = {sx,sy};posb[b] = {1,1};

    while(qa.size() && qb.size()){
        if(disa[qa.front()] + disb[qb.front()] > 20) return -1;
        if(qa.size() <= qb.size()){ //谁目前扩展的少就去扩展谁
            int res = extentA();
            if(res!=-1 && res<=20) return res;
            if(res>20) return -1;
        }else{ //扩展B时，交换一下指针就好
            swap(qa,qb);
            swap(disa,disb);
            swap(posa,posb);
            int res = extentA();
            if(res!=-1 && res<=20) return res;
            if(res>20) return -1;
            swap(qa,qb);
            swap(disa,disb);
            swap(posa,posb);
        }
    }

    return -1;
}

int main(){
    cin>>T;
    while(T--){
        a = '-';b = "-011222333344444555555";//以字符串存储状态，下标从1开始
        char c;
        for(int i = 1;i<=6;i++){
            for(int j = 1;j<=i;j++){
                scanf(" %c",&c);
                a+=c;
                if(c == '0')
                    sx = i,sy = j;
            }
        }
        if(a == b) puts("0");
        else{
            int res = bfs();
            if(res == -1) puts("too difficult");
            else cout<<res<<endl;
        }

    }


    return 0;
}

双向BFS+Hash

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
typedef unsigned long long ull;
int dir[4][2] = {-1,0,-1,-1,1,0,1,1};
int T;
struct node{
    ull x,y;
    ull hs;
    int st[7][7];
}sta,stb;

ull Hash(node &no){
    ull hs = 0;
    for(int i =0;i<6;i++){
        for(int j = 0;j<=i;j++){
            hs = hs<<3|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++){
        ull dx = cur.x+dir[i][0];
        ull dy = cur.y+dir[i][1];
        if(dx<0 || dx>5 || dy<0 || dy> dx) continue;
        node ne = cur;
        swap(ne.st[cur.x][cur.y],ne.st[dx][dy]);
        ne.x = dx,ne.y = 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(){
    queue<node> qa,qb;
    unordered_map<ull,int> disa,disb;
    qa.push(sta);qb.push(stb);
    disa[sta.hs] = 0;disb[stb.hs] = 0;
    while(qa.size() && qb.size()){
        if(disa[qa.front().hs] + disb[qb.front().hs]>20) return -1;
        int res;
        if(qa.size()<= qb.size()){
            res = ex(qa,disa,disb);
        }else{
            res = ex(qb,disb,disa);
        }
        if(res!=-1 && res<=20) return res;
        if(res>20) return -1;//需注意
    }
    return -1;
}

int main(){
    cin>>T;
    while(T--){
        for(int i = 0;i<6;i++){
            for(int j = 0;j<=i;j++){
                scanf("%d",&sta.st[i][j]);
                stb.st[i][j] = i;
                if(sta.st[i][j] == 0){
                    sta.x = i,sta.y = j;
                }
            }
        }
        stb.x = 0,stb.y = 0;
        stb.hs = Hash(stb);
        sta.hs = Hash(sta);
        if(sta.hs == stb.hs) puts("0"); //初始状态也需要判断
        else{
            int res = bfs();
            if(res == -1) puts("too difficult");
            else cout<<res<<endl;
        }

    }
    return 0;
}