AcWing 845. 八数码

/*y总写法，因为蓝桥杯不支持c++11，本题用map会超时，所以下面使用的是手写hash
#include <bits/stdc++.h>
using namespace std;
queue<string> q;
unordered_map<string,int> d;
int bfs(string start){
    string end="12345678x";
    
    q.push(start);
    d[start]=0;
    
    while(q.size()){
        string t=q.front();
        q.pop();
        int distance=d[t];
        int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
        if(t==end) return distance;
        //状态转移，返回x在字符串中的下标
        int k=t.find('x');
        //计算出x在数组中的位置
        int x=k/3,y=k%3;
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3){
                //a*3+b数组中的位置转为字符串的位置
                //状态更新
                swap(t[k],t[a*3+b]);
                if(!d.count(t)){
                    d[t]=distance+1;
                    q.push(t);
                }
                //还原状态               
                swap(t[k],t[a*3+b]);
            }
        }
    }
    return -1;
}
int main(){
    string start;
    for(int i=0;i<9;i++){
        char c;
        cin>>c;
        start+=c;
    }
    cout<<bfs(start)<<endl;
    return 0;
}
*/
#include <iostream>
#include <queue>
#include <cstring>
//手写hash，把字符串转为数值，再根据数值找位置。再把数值赋给下标。
//https://www.acwing.com/solution/content/12584/
using namespace std;
struct node
{
    string map;
    int distance;
};
const int M=4e6+10,null=0x3f3f3f3f;
unsigned long long ha[9];
int h[M],b;
//哈希寻找对应坐标
int m_find(int x)
{
    int k=(x%M+M)%M;
    while(h[k]!=null&&h[k]!=x)
    {
        k++;
        if(k==M)k=0;
    }
    return k;
}
//字符串转化为唯一的序列，再通过序列求出在h数组中的下标
void s_to(string tmp){
    for(int i=1;i<10;i++)
        {
            char ccc=tmp[i];
            ha[i]=ha[i-1]*131+ccc;
        }
}
void bfs(string c)
{
    queue<node > q;
    q.push({c,0});
    string end="12345678x";
    //可移动的四个方向：上下左右
    int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
    while(!q.empty())
    {
        node p=q.front();
        q.pop();
        
        //将字符串转为数值
        s_to(p.map);
        //把唯一的ha[9]赋值给通过哈希后寻找的h[下标]
        h[m_find(ha[9])]=ha[9];
        if(p.map==end)
        {
            cout<<p.distance<<endl;
            return ;
        }
        string k=p.map;
        int x=k.find('x')/3,y=k.find('x')%3;
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx>=0&&ny>=0&&nx<3&&ny<3){
                swap(p.map[x*3+y],p.map[nx*3+ny]);
                s_to(p.map);
            if(h[m_find(ha[9])]==null)
                q.push({p.map,p.distance+1});
            swap(p.map[x*3+y],p.map[nx*3+ny]);
            }
        }
    }
    cout<<"-1\n";
}
int main()
{
    memset(h,0x3f,sizeof h);
    string start;
    char c;
    for(int i=0;i<9;i++)
       {
           cin>>c;
           start+=c;
       }
    bfs(start);
    return 0;
}