分析

见y总的 八数码视频讲解

思路参考 我的八数码题解

这里只有一点点不同，出口方式改变了。

C++ 1355ms

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>

#define ffor(i,s,e) for(int i=s;i<e;i++)
using namespace std;

const int M =1e7+100;
int dist[M];

basic_string<char>::size_type posA,posB;

const int dir[4][2]={
    {1,0},{0,1},{-1,0},{0,-1}
};


int hashToI(string s){//状态字符串映射为下标
    const char* str=s.c_str();

    int hash = 0;
    for (int i=0; *str; i++)
    {
        if (i & 1)//奇数时
        {
            hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
        }
        else
        {
            hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
        }
    }

    return (hash & 0x7FFFFFFF)%M;
}


int hashToI1(string s){
    int seed=13131313;
    int hash=0;

    const char* str=s.c_str();
    while(*str){
        hash=hash*seed+(*str++);
        if(*str=='*') hash++;
    }

    return (hash&0x7fffffff)&M;
}
bool check(int nx,int ny){
    return nx>=0&&nx<2&&ny>=0&&ny<3;
}

int bfs(string start){
    queue<string> q;
    q.push(start);
    dist[hashToI(start)]=0;


    while(q.size()){

        string now=q.front();q.pop();

        int nowi=hashToI(now);
        int nowd=dist[nowi];
        if(now.find('A')==posB&&now.find('B')==posA){
            // cout<<now<<endl;
            return nowd;
        }


        //确定当前位置 （x,y）
        int k=now.find(' ');
        int x=k/3,y=k%3;

        ffor(i,0,4){
        //尝试下一个位置(next x,next y)
            int nx=x+dir[i][0];
            int ny=y+dir[i][1];

            if(check(nx,ny)){
                swap(now[k],now[nx*3+ny]);//变成下一个状态

                int nxti=hashToI(now);
                if(!dist[nxti]){//未被访问过
                    dist[nxti]=nowd+1;
                    q.push(now);
                }
                swap(now[k],now[nx*3+ny]);//恢复现场

            }
        }

    }
    return -1;
}


int main(){
    string start;
    string tmp;
    getline(cin,tmp);
    start+=tmp;
    getline(cin,tmp);
    start+=tmp;

    posB=start.find('B');
    posA=start.find('A');

   // cout<<posA<<posB<<endl;
    cout<<bfs(start)<<endl;


    // cout<<start<<endl;
    // cout<<hashToI(start)<<endl;
    return 0;
}