程序代码：

#include <stdio.h>
#include <string.h>
typedef int State[9];//状态类型 存储八数码 
State queue[100000];//队列 
int step[100000];//对应结点到根结点的距离，即步骤 
const int dx[] = {0,0,1,-1};//定义方向 
const int dy[] = {-1,1,0,0};
int front,rear;
const int MAXHASHSIZE = 1000003;
int head[MAXHASHSIZE],next[MAXHASHSIZE];

int vis[36288],fact[9];
int bfs(State &r,State & g);
int main(){
    State root,goal;
    while(1){
        for(int i = 0; i < 9; i++)
            scanf("%d",&root[i]);
        for(int i = 0; i < 9; i++)
            scanf("%d",&goal[i]);
        int ans = bfs(root,goal);
        if(ans > 0)
            printf("%d ",step[ans]);
        else
            printf("-1\n");
    }
}
int bfs(State & r,State &g){
    init_lookup_table();
    memset(step,0,sizeof(step));//初始化所有状态对应步骤 
    front = rear = 0;
    memcpy(queue[rear++],r,sizeof(r));//跟结点入队列 
    while(front < rear){ 
        State v;
        memcpy(v,queue[front++],sizeof(v));//出队列
        if(memcmp(v,g,sizeof(g)) == 0) 
            return front - 1;
        int z;
        for(z = 0 ; z < 9 ; z++)
            if(!v[z])
                break;
        int xx = z / 3;              //行号 
        int yy = z % 3;              //列号 
        for(int d = 0 ; d < 4 ; d++){//扫描四个方向 
            int newx = xx + dx[d];//新方向 
            int newy = yy + dy[d]; 
            if(newx >=0 && newx <= 2 && newy >=0 && newy <= 2){//如果该方向合法，则入队列 
                int k = 3 * newx + newy; //记录下这个方向的编号 
                State u;
                memcpy(u,v,sizeof(v)); 
                u[z] = u[k];// 实现移动 
                u[k] = 0;
                memcpy(queue[rear],u,sizeof(u));//入队列 
                step[rear - 1] = step[front - 1] + 1;//更新对应结点的所对应步骤 
                if(try_to_insert(rear))
                    rear++; 
            } 
        }
    }
}

程序代码：

#include <stdio.h>
#include <string.h>
typedef int State[9];
const int MAXSTATE = 1000000;
State st[MAXSTATE],goal;
int dist[MAXSTATE];
const int dx[] = {-1,1,0,0};
const int dy[] = {0,0,-1,1};
const int MAXHASHSIZE = 1000003;
int head[MAXHASHSIZE];
int next[MAXSTATE];
void init_lookup_table(){
    memset(head,0,sizeof(head));
}
int hash(State &v){
    int j = 0;
    for(int i = 0; i < 9; i++){//除留余数法算hash
        j = j * 10 + v[i];
    }
    return j % MAXHASHSIZE;
}

int try_insert(int s){//相当于静态链表
    int h = hash(st[s]);//获取st[s]状态的hash值
    int u = head[h];//获取哈下表映射上存的链表首结点
    while(u){// u == 0 表示为链表为空或者指针指向NULL
        
        if(memcmp(st[u],st[s],sizeof(st[s])) == 0)//要插入的状态已经存在
            return 0;//返回0表示错误,即防止其往回走，这是为了去掉图中的环
        u = next[u];     
    } 
    next[s] = head[h];
    head[h] = s;
    return 1;
}

int bfs(){
    init_lookup_table();
    int front = 1, rear = 2;//这里之所以不使用下标零，是因为在上面的链表中，把0视为不存在，即链表中的NULL 
    while(front < rear){
        State &s = st[front];
        if(memcmp(goal,s,sizeof(s)) == 0 )
            return front;
        int z;
        for(z = 0; z < 9; z++)
            if(!s[z])
                break;
        int x = z/3;//行号 
        int y = z % 3;//列号 
        for(int d = 0; d < 4; d++){//扫描空格周围的四个方向 
            int newx = x + dx[d];
            int newy = y + dy[d];
            int newz = newx * 3 + newy;
            if(newx >= 0 && newx < 3 && newy >=0 && newy < 3){
                State &t = st[rear];
                memcpy(&t,&s,sizeof(s));
                t[newz] = s[z];
                t[z] = s[newz];
                dist[rear] = dist[front] + 1;
                if(try_insert(rear))
                    rear++;
            }
        }
        front++;
    }
    return 0;
}
int main(){
    for(int i = 0; i < 9; i++)
        scanf("%d",&st[1][i]);
    for(int i = 0; i < 9; i++)
        scanf("%d",&goal[i]);
    int ans = bfs();
    if(ans > 0)
        printf("%d\n",dist[ans]);
    else
        printf("-1\n");
    return 0;
}