2687: C 8数码问题 哈西表

#include<iostream>
#include<string>
#include<cstdio>
#include<queue>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
const int HASHING=600001;
int hash_table[HASHING+1];
int hash(int x)//构建哈希表
{
    int ret;
    ret=x%HASHING;
    while(hash_table[ret]!=-1&&hash_table[ret]!=x) ret=(ret+1)%HASHING;
    hash_table[ret]=x;
    return ret;
}//important
int num(string str)
{
    int t=0;
    for(int i=0;i<str.size();i++)
    {
        t=t*10+str[i]-'A';
    }
    return t;
}
int xx[4]={0,0,1,-1};
int yy[4]={1,-1,0,0};
struct Node
{
    string str;
    int l;
};
Node pre,end;
int vis[600000];
int bfs()
{
    queue<Node> q;
    q.push(pre);
    while(!q.empty())
    {
        Node temp=q.front();q.pop();
        int p;
        for(int i=0;i<9;i++) if(temp.str[i]=='A') {p=i;break;}
        int x=p/3,y=p%3;
        for(int i=0;i<4;i++)
        {
            int x1=x+xx[i],y1=y+yy[i];
            if(x1<0||x1>=3||y1<0||y1>=3) continue;
            int t=x1*3+y1;
            //cout<<temp.str<<endl;
            //cout<<"t="<<t<<endl;
            Node later;
            later.l=temp.l+1;
            later.str=temp.str;
            swap(later.str[p],later.str[t]);
            //cout<<"..."<<later.str<<endl;
           if(vis[hash(num(later.str))])
           {
               continue;
           }
            if(later.str==end.str)
            {
               // cout<<later.l<<"..."<<endl;
                return later.l;
            }
            else
            {
                q.push(later);
                vis[hash(num(later.str))]=1;
            }
        }
    }
    //cout<<"ok"<<endl;
    return 0;
}
int main()
{
   // freopen("out.txt","w",stdout);
    string ch;
    int pl=1;
    int ci;cin>>ci;
    while(ci--)
    {
        memset(hash_table,-1,sizeof(hash_table));//初始化哈希表  important
        memset(vis,0,sizeof(vis));
        pre.str.clear();end.str.clear();
        pre.l=0;
        for(int i=0;i<9;i++) {cin>>ch;pre.str+=ch;}
        vis[hash(num(pre.str))]++;
        for(int i=0;i<9;i++) {cin>>ch;end.str+=ch;}
        int cnt;
        if(pre.str==end.str) cnt=0;
        else cnt=bfs();
        //cout<<cnt<<endl;
        cout<<"Battle array #"<<pl++<<" :"<<endl;
        cout<<"The minimum move of the battle array is : "<<cnt<<endl;
        cout<<endl;
    }
    return 0;
}