算法1

(手写hash)

注：蓝桥杯可使用map(有序)函数，但此题测试用例会超时

#include<bits/stdc++.h>
using namespace std;
//该结点是将二维数组状态压缩成一个字符串
typedef unsigned long long ULL;
const int M=10000000;
const int N=100010,P=13331;
ULL h[N];//h[]存放字符串的前缀值
int d[M];
ULL hash_CSM(string a)
{
    h[0]=0;
    for(int i=1;i<=9;i++)
    {
        h[i]=h[i-1]*P+(a[i-1]-'0'+1);

    }
    return h[9]%M;
    //y总讲hash时用ULL实现自动取余，但是此题hash值需要作为数组下标，对该结点进行标记，所以通过多次试验，找到M可实现不冲突，且数组可开辟这些空间
}
int bfs(string state)
{
    queue<string>q;//队列存放节点 
    //unordered_map<string,int>d;//存放到达该结点的最短步数(d[string]的值) 

    q.push(state); //节点入队 
    //cout<<hash(state);
    d[hash_CSM(state)]=0;//到达该结点的步数为零步 
    string end="12345678x";
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};//遍历当前状态下该结点上下左右四个方向 
    while(q.size())//队列中有节点 
    {
        string t=q.front();//临时变量t等于队列中的头结点 
        q.pop();//出队 
        if(t==end)return d[hash_CSM(t)];//找到答案，返回最短路径 
        int distance=d[hash_CSM(t)];//临时变量distance存放到达当前节点的最短路径 
        /*为什么需要distance临时变量？ 
        因为下面改变字符串后，字符串t更新，找不到该状态下的上一个状态*/ 
        int k=t.find('x');//找到可变换节点的坐标 
        int x=k/3,y=k%3;//转换为二维，为了寻找其上下左右四个节点 
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i];
            int b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3)
            {


                swap(t[a*3+b],t[k]);
                //在一维中将符合条件的节点和可变换节点进行位置交换 
                //cout<<t<<endl;
                //cout<<"字符串的哈希值"<<hash(t)<<endl;
                //cout<<"到该节点的步数"<<d[hash(t)]<<endl;
                if(!d[hash_CSM(t)])//d数组初始化时0，是0代表该结点 未被访问过 
                {

                    d[hash_CSM(t)]=distance+1;
                    q.push(t);  
                } 
                swap(t[a*3+b],t[k]);//字符串恢复到原来，继续遍历下种状态是否可行 
            }

        }
    }
    return -1; 
}
int main()
{
    string state;

    char c;
    for(int i=0;i<9;i++)
    {
        cin>>c;
        state+=c;
    }

    cout << bfs(state) << endl;

    return 0;
}

算法2

(用unordered_map函数)

#include<bits/stdc++.h>
using namespace std;
//该结点是将二维数组状态压缩成一个字符串 
int bfs(string state)
{
    queue<string>q;//队列存放节点 
    unordered_map<string,int>d;
    //存放到达该结点的最短步数(d[string]的值) 
    q.push(state); //节点入队 
    d[state]=0;//到达该结点的步数为零步 
    string end="12345678x";
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    //遍历当前状态下该结点上下左右四个方向 
    while(q.size())//队列中有节点 
    {
        string t=q.front();//临时变量t等于队列中的头结点 
        q.pop();//出队 
        if(t==end)return d[t];
        //找到答案，返回最短路径 
        int distance=d[t];
        //临时变量distance存放到达当前节点的最短路径 
        /*为什么需要distance临时变量？ 
        因为下面改变字符串后，字符串t更新，找不到该状态下的上一个状态*/ 
        int k=t.find('x');
        //找到可变换节点的坐标 
        int x=k/3,y=k%3;
        //转换为二维，为了寻找其上下左右四个节点 
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i];
            int b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3)
            {
                swap(t[a*3+b],t[k]);
                //在一维中将符合条件的节点和可变换节点进行位置交换 
                if(!d.count(t))
                {
                    d[t]=distance+1;
                    q.push(t);  
                } 
                swap(t[a*3+b],t[k]);
                //字符串恢复到原来，继续遍历下种状态是否可行 
            }

        }
    }
    return -1; 
}
int main()
{
    string state;
    char c;
    for(int i=0;i<9;i++)
    {
        cin>>c;
        state+=c;
    }

    cout << bfs(state) << endl;

    return 0;
}