题目描述：

八数码问题，只是需要输出具体的变换方案，而且要其字典序最小。

解题报告：

大部分的八数码题目只是要输出最短的步数，即使要求输出方案也都是spj。

双向广搜和A*都可以很好的解决最短步数的问题。

但是字典序最小的话，单向按照字典序广搜可以得到答案，但是会超时。

（比赛时候我写的单广跑赛后官方数据要20s多，题目给了5s，不知道努力优化一把能不能过）

赛后写的双向广搜过了：

正向：直接按照dlru的顺序搜索就可以保证字典序。

反向：从末状态开始搜，如果搜到状态x

如果x状态没有被访问，那么访问它。

如果x状态已经访问了，（这里保证字典序最小的关键步骤）

那么找出原来的 从x状态到末状态的操作字符串

还有：         当前再次访问x的那一步的从x到末状态的操作字符串。

两者取一个最小的，使x的状态的前驱标记始终是最小的那个即可。

代码如下：116行

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
int move[2][4][2] = {{{1, 0}, {0, -1}, {0, 1}, {-1, 0}}, {{-1, 0}, {0, 1}, {0, -1}, {1, 0}}}, t;
char mv[4] = {'d', 'l', 'r', 'u'};
int pos[9][2] = {{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}};
int frc[10], vst[2][370000];
struct jeo
{
    char str[10], o;
    int pre, s, pos;
}que[2][370000];
void init()
{
    frc[0] = 1;
    for(int i = 1; i <= 9; i++) frc[i] = i * frc[i - 1];
}
int hash(char *str)//计算Hash值
{
    int v = 0;
    for(int i = 0; i < 9; i++)
    {
        int a = str[i] - '0', cnt = 0;
        for(int j = i + 1; j < 9; j++)
            if (str[j] - '0' < a) cnt++;
        v += cnt * frc[a - 1];
    }
    return v;
}
string ans, ans0, ans1;
void getans0(int id)
{
    if (id == -1) return;
    getans0(que[0][id].pre);
    if (que[0][id].pre != -1)
        ans0 += que[0][id].o;
}
void getans1(int id)
{
    if (id == -1) return;
    if (que[1][id].pre != -1)
        ans1 += que[1][id].o;
    getans1(que[1][id].pre);
}
int main()
{
    scanf("%d", &t); init();
    for(int ca = 1; ca <= t; ca++)
    {
        int head[2], tail[2]; head[0] = head[1] = tail[0] = tail[1] = 1;
        memset(vst, 0, sizeof(vst));
        for(int i = 0; i < 2; i++)
        {
            scanf("%s", que[i][tail[i]].str);
            for(int j = 0; j < 9; j++)
                if (que[i][tail[i]].str[j] == 'X')
                {
                    que[i][tail[i]].pos = j;
                    que[i][tail[i]].str[j] = '9';
                }
            vst[i][hash(que[i][tail[i]].str)] = 1;
            que[i][tail[i]].s = 0;
            que[i][tail[i]++].pre = -1;
        }
        if (strcmp(que[0][1].str, que[1][1].str) == 0)
        {
            printf("Case %d: 0\n\n", ca); continue;
        }
        bool flag = false; ans = "";
        int count = 0;
        for(int i = 0; (head[0] < tail[0] || head[1] < tail[1]) && !flag; i = (i + 1) % 2)
        {
            int pre = que[i][head[i]].s;
            while(head[i] < tail[i])
            {
                jeo jeogia = que[i][head[i]];
                if (jeogia.s != pre) break;
                else head[i]++;
                for(int j = 0; j < 4; j++)
                {
                    jeo tmp = jeogia;int a = pos[tmp.pos][0], b = pos[tmp.pos][1];
                    a += move[i][j][0], b += move[i][j][1];
                    if (!(a >= 0 && a < 3 && b >= 0 && b < 3)) continue;
                    swap(tmp.str[a * 3 + b], tmp.str[jeogia.pos]);
                    tmp.s = jeogia.s + 1; tmp.o = mv[j]; tmp.pre = head[i] - 1;
                    tmp.pos = a * 3 + b; que[i][tail[i]] = tmp;
                    int key = hash(tmp.str);
                    if (!vst[i][key])
                        vst[i][key] = tail[i]++;
                    else if(i == 1)
                    {
                        ans1 = "";getans1(tail[i]);
                        string temp = ans1; ans1 = "";
                        getans1(vst[i][key]);
                        if(temp.length() < ans1.length() || temp.length() == ans1.length() && temp < ans1)
                            que[1][vst[i][key]] = que[1][tail[i]];
                    }
                    if (vst[i ^ 1][key])
                    {
                        flag = true; string tt; ans0 = ans1 = "";
                        int a = vst[i][key], b = vst[i ^ 1][key];
                        if (i) swap(a, b);
                        getans0(a); getans1(b);
                        tt = ans0 + ans1;
                        if (ans == "" || tt.length() < ans.length() || (tt.length() == ans.length() && tt < ans))
                            ans = tt;
                    }
                }
            }
        }
        printf("Case %d: %d\n", ca, ans.length());
        printf("%s\n", ans.c_str());
    }
}