八数码问题（紫薯P199）

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using namespace std;
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};
set<int> vis;
/*
void init_lookup_table()
{
    vis.clear();
}
int try_to_insert(int s)
{
    int v = 0;
    for(int i = 0; i < 9; i++)
        v = v * 10 + st[s][i];
    if(vis.count(v))
        return 0;
    vis.insert(v);
    return 1;
}
*/
const int hashsize = 1000003;
int head[hashsize], Next[maxstate];
void init_lookup_table()
{
    memset(head, 0, sizeof(head));
}
int Hash(State &s)
{
    int v = 0;
    for(int i = 0; i < 9; i++)
        v = v * 10 + s[i];
    return v % hashsize;
}
int try_to_insert(int s)
{
    int h = Hash(st[s]);
    int u = head[h];
    while(u)
    {
        if(memcmp(st[u], st[s], sizeof(st[s])) == 0)
            return 0;
        u = Next[u];
    }
    Next[s] = head[h];
    head[h] = s;
    return 1;
}
int bfs()
{
    init_lookup_table();
    int first = 1, last = 2;
    dist[1] = 0;
    while(first < last)
    {
        State &s = st[first];
        if(memcmp(goal, s, sizeof(s)) == 0)
            return first;
        int z;
        for(z = 0; z < 9; z++)
            if(s[z] == 0)
                break;
        int x = z / 3;
        int y = z % 3;
        for(int i = 0; i < 4; i++)
        {
            int fx = x + dx[i];
            int fy = y + dy[i];
            int fz = fx * 3 + fy;
            if(fx >= 0 && fy >= 0 && fx < 3 && fy < 3)
            {
                State &t = st[last];
                memcpy(&t, &s, sizeof(s));
                t[fz] = s[z];
                t[z] = s[fz];
                dist[last] = dist[first] + 1;
                if(try_to_insert(last))
                    last++;
            }
        }
        first++;
    }
    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
", dist[ans]);
    else
        printf("-1
");
    return 0;
}
/*
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
*/