一.题目链接：

HDU-1043

二.题目大意：

八数码经典问题.

不懂的去玩 4399

三.分析：

挂上几个大佬的链接：

八数码解的存在性证明

康拓展开

直接 BFS TLE 了.

这里 反向 BFS 很妙，只搜索一次，把所有状态都记录下来.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-6
#define pi acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)5e5;

struct node
{
    int D[9];
    int x;
    int y;
};

struct node start;

int son[M + 5];
bool vis[M + 5];

char dir[M + 5];

int Move[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int Reverse_Num()
{
    int cnt = 0;
    for(int i = 0; i < 9; ++i)
    {
        for(int j = 0; j < i; ++j)
        {
            if(start.D[i] && start.D[j] && start.D[j] > start.D[i])
                cnt++;
        }
    }
    return cnt;
}

int cantor(struct node p)
{
    int sum = 0;
    int fac = 40320;
    for(int i = 0; i < 9; ++i)
    {
        int cnt = 0;
        for(int j = i + 1; j < 9; ++j)
        {
            if(p.D[j] < p.D[i])
                cnt++;
        }
        sum += fac * cnt;
        if(i == 8)
            return sum;
        fac /= 8 - i;
    }
}

void bfs()
{
    struct node p, t;
    for(int i = 0; i < 8; ++i)
        p.D[i] = i + 1;
    p.D[8] = 0;
    p.x = p.y = 2;
    queue <node> q;
    q.push(p);
    int can1, can2;
    can1 = cantor(p);
    vis[can1] = 1;
    while(!q.empty())
    {
        p = q.front();
        q.pop();
        can1 = cantor(p);
        for(int i = 0; i < 4; ++i)
        {
            t = p;
            t.x += Move[i][0];
            t.y += Move[i][1];
            if(t.x < 0 || t.x >= 3 || t.y < 0 || t.y >= 3)
                continue;
            int pos = t.x * 3 + t.y;/// r l d u
            if(i == 0)
            {
                swap(t.D[pos], t.D[pos - 1]);
                can2 = cantor(t);
                if(!vis[can2])
                {
                    vis[can2] = 1;
                    dir[can2] = 'l';
                    son[can2] = can1;
                    q.push(t);
                }
            }
            else if(i == 1)
            {
                swap(t.D[pos], t.D[pos + 1]);
                can2 = cantor(t);
                if(!vis[can2])
                {
                    vis[can2] = 1;
                    dir[can2] = 'r';
                    son[can2] = can1;
                    q.push(t);
                }
            }
            else if(i == 2)
            {
                swap(t.D[pos], t.D[pos - 3]);
                can2 = cantor(t);
                if(!vis[can2])
                {
                    vis[can2] = 1;
                    dir[can2] = 'u';
                    son[can2] = can1;
                    q.push(t);
                }
            }
            else if(i == 3)
            {
                swap(t.D[pos], t.D[pos + 3]);
                can2 = cantor(t);
                if(!vis[can2])
                {
                    vis[can2] = 1;
                    dir[can2] = 'd';
                    son[can2] = can1;
                    q.push(t);
                }
            }
        }
    }
}

int main()
{
    bfs();
    char ch;
    while((ch = getchar()) > 0)
    {
        int pos = 0;
        while(ch != '\n')
        {
            if(ch >= '0' && ch <= '8')
                start.D[pos++] = ch - '0';
            else if(ch == 'x')
                start.D[pos++] = 0;
            ch = getchar();
        }
        if(Reverse_Num() & 1)
        {
            printf("unsolvable\n");
            continue;
        }
        int can = cantor(start);
        while(can != 46233)
        {
            printf("%c", dir[can]);
            can = son[can];
        }
        printf("\n");
    }
    return 0;
}