双向广搜求解八数码问题.txt

双向广搜求解八数码问题,双向广搜求解八数码问题

#include <iostream>
#define Prime 99991
#define MAX_LEN 120000

int hashTable[MAX_LEN][2];
int adj[][5] = {{1,3,-1},{0,2,4,-1},{1,5,-1},{0,4,6,-1},{1,3,5,7,-1},{2,4,8,-1},{3,7,-1},{4,6,8,-1},{5,7,-1}};
int src[9],dst[9],tmp[9];

int getHashID(int val)
{
    int hashID;
    hashID = val % Prime;
    return hashID;
}

int find(int val,int ch,int &_hashid)
{
    int hashID;
    hashID = getHashID(val);
    while(hashTable[hashID][ch] != -1 && hashTable[hashID][ch] != val) 
    {
        hashID++;
        if(hashID == MAX_LEN) hashID = 0;
    }
    _hashid = hashID;
    if(hashTable[hashID][ch] == -1) return -1;
    else return hashID;
}

int insert(int val,int ch)
{
    int hashID;
    hashID = getHashID(val);
    while(hashTable[hashID][ch] != -1) 
    {
        hashID++;
        if(hashID == MAX_LEN) hashID = 0;
    }
    hashTable[hashID][ch] = val;
    return hashID;
}

bool check()
{
    int i,j;
    int s1=0,s2=0;
    for(i=0;i<9;i++)
        for(j=0;j<i;j++)
        {
            if (src[i] > src[j] && (src[i] && src[j])) s1++;
            if (dst[i] > dst[j] && (dst[i] && dst[j])) s2++;
        }
    return s1 % 2 == s2 % 2;
}

int toNum(int str[9])
{
    int i,num = 0;
    for(i=0;i<9;i++)
    {
        num = num * 10 + str[i];
    }
    return num;
}

void toArray(int val)
{
    int i;
    for(i=8;i>=0;i--)
    {
        tmp[i] = val % 10;
        val /= 10;
    }
}

int QueF[MAX_LEN];
int StepF[MAX_LEN];
int QueB[MAX_LEN];
int StepB[MAX_LEN];

int BFS()
{
    int Ffront,Bfront,Ftail,Btail,Ft,Bt;
    int i,j,k,val,step,hashID,tmpid;
    
    memset(hashTable,-1,sizeof(hashTable));
    if(!check()) return -1;
    if(toNum(src)==toNum(dst)) return 0;
    
    val = toNum(src);
    QueF[0] = val;
    tmpid = insert(val,0);
    StepF[tmpid] = 0;
    val = toNum(dst);
    QueB[0] = val;
    insert(val,1);
    StepB[tmpid] = 0;
    step = 1;
    Ftail = Btail = 1;
    Ffront = Bfront = 0;

    while(1)
    {
        //
        Ft = Ftail;
        for(i = Ffront; i < Ft; i++)
        {
            toArray(QueF[i]);
            for(j = 0; j < 9; j++)
                if(tmp[j] == 0) break;
            for(k = 0; adj[j][k] != -1; k++)
            {
                tmp[j] = tmp[adj[j][k]];
                tmp[adj[j][k]] = 0;
                val = toNum(tmp);
                if(find(val,0,hashID)==-1)
                {
                    hashTable[hashID][0] = val;
                    StepF[hashID]  = step;
                    tmpid = find(val,1,hashID);
                    QueF[Ftail++] = val;
                    if(tmpid!=-1)
                    {
                        //puts("FRONT TABLE");for(int ii=0;ii<Ftail;ii++) printf("%d %d\n",QueF[ii],StepF[find(val,0,hashID)]);
                        return step + StepB[tmpid];
                    }
                }
                tmp[adj[j][k]] = tmp[j];
                tmp[j] = 0;
            }
        }
        Ffront = Ft;
        //
        Bt = Btail;
        for(i = Bfront; i < Bt; i++)
        {
            toArray(QueB[i]);
            for(j = 0; j < 9; j++)
                if(tmp[j] == 0) break;
            for(k = 0; adj[j][k] != -1; k++)
            {
                tmp[j] = tmp[adj[j][k]];
                tmp[adj[j][k]] = 0;
                val = toNum(tmp);
                if(find(val,1,hashID)==-1)
                {
                    hashTable[hashID][1] = val;
                    StepB[hashID]  = step;
                    tmpid = find(val,0,hashID);
                    QueB[Btail++] = val;
                    if(tmpid!=-1)
                    {
                        /*printf("%d\n",val);
                        puts("FRONT TABLE");
                        for(int ii=0;ii<Ftail;ii++) printf("%d %d\n",QueF[ii],StepF[find(QueF[ii],0,hashID)]);
                        puts("TAIL TABLE");
                        for(int ii=0;ii<Btail;ii++) printf("%d %d\n",QueB[ii],StepB[find(QueB[ii],1,hashID)]);*/
                        return step + StepF[tmpid];
                    }
                }
                tmp[adj[j][k]] = tmp[j];
                tmp[j] = 0;
            }
        }
        Bfront = Bt;
        step++;
    }
}

int main()
{
    int i;
    for(i=0;i<9;i++)
    {
        scanf("%d",&src[i]);
    }
    for(i=0;i<9;i++)
    {
        scanf("%d",&dst[i]);
    }
    printf("%d\n",BFS());
    return 0;
}