题目描述：经典8数码问题，不再赘述。

    分析：状态仅有9！，不到40万，广搜即可满足题目要求，重点是怎样记录某个状态是否走过。

    在这里，我的的是哈希，x用数字9代替，这样每个状态可以用一个9位数的整数来表示，int即可。

    大概用一个50W的数组来哈希就差不多了。

    每一个节点存：当前x的位置，他前一个状态在队列中的下标（用于输出用），当前状态（9个数字），当前执行的步骤（u，d,l,r)。剩下的就是朴素的广搜了。

#include<iostream>
#include<string>
using namespace std;
#define M 711111
char pos[4] = {'u', 'd', 'l', 'r'};
int move[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int hash[M];
struct p
{
    int x, y, from;
    char key[9], o;
}que[365000];
string str[9];
int H(int key)
{
    int pos = key % M;
    while(!(!hash[pos] || hash[pos] == key))
        if ( pos == M)
            pos = 0;
    return pos;
}
void op(int i)
{
    if (i == -1)
        return;
    if (que[i].from != -1)
    {
        op(que[i].from);
        putchar(que[i].o);
    }
}
int kk;
int main()
{
    int head = 0, tail = 0;
    kk = 0;
    memset(hash, 0, sizeof(hash));
    for(int i = 0; i < 3; i )
        for(int j = 0; j < 3; j )
        {
            cin >> str[i * 3 j];
            que[tail].key[i * 3 j] = str[i * 3 j][0];
            if (que[tail].key[i * 3 j] == 'x')
            {
                que[tail].key[i * 3 j] = '9';
                que[tail].x = i, que[tail].y = j;
                que[tail].from = -1;
            }
            kk *= 10, kk = que[tail].key[i * 3 j] - '0';
        }
    hash[H(kk)] = kk;
    tail ;
    bool flag;
    while(head < tail)
    {
        flag = true;
        for(int i = 1; i <= 9; i )
            if (que[head].key[i - 1] != '0' i)
            {
                flag = false;
                break;
            }

        if (flag)
            break;
        int x = que[head].x, y = que[head].y;
        for(int i = 0; i < 4; i )
        {
            int a = x move[i][0], b = y move[i][1];
            for(int j = 0; j < 9; j )
                que[tail].key[j] = que[head].key[j];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                char temp = que[tail].key[x * 3 y];
                que[tail].key[x * 3 y] = que[tail].key[a * 3 b];
                que[tail].key[a * 3 b] = temp;
                kk = 0;
                for(int j = 0; j < 9; j )
                    kk *= 10, kk = que[tail].key[j] - '0';
                int pp = H(kk);
                if (!hash[pp])
                {
                    hash[pp] = kk;
                    que[tail].x = a;
                    que[tail].y = b;
                    que[tail].o = pos[i];
                    que[tail].from = head;
                    tail ;
                }
            }
        }
        head ;
    }
    if (flag)
    {
        op(head);
        putchar('\n');
    }
    else
        printf("unsolvable\n");
    return 0;
}