【题目链接】:http://acm.hdu.edu.cn/showproblem.php?pid=1043

【题意】



会给你很多组数据;

让你输出这组数据到目标状态的具体步骤;

【题解】



从12345678x这个目标状态开始bfs然后获取它能够到达的所有状态;

然后在队列中记录下执行这一步用的是那个操作;

递归输出就好;

map来判定这状态存不存在;

在队列里面存这个状态

就按照所给的存成1维的数组就好;

x用9代替;(用0也可以哦);

模拟八数码的操作就好;

因为是逆序的,所以记录的操作是相反的;

最后递归写输出的时候搞晕了；

又WA了好多次.



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 200e4;

const int chushi[10] = { 0,1,2,3,4,5,6,7,8,9 };

struct abc

{

    int s[15];

    int pos,ope,pre;

};

map<int, int> dic;

abc dl[N];

int ts[15];

string t;

int zt(int s[15])

{

    int r = 0;

    rep1(i, 1, 9)

        r = r * 10 + s[i];

    return r;

}

void bfs()

{

    abc temp,temp1;

    rep1(i, 0, 9) temp.s[i] = chushi[i];

    temp.pos = 9;

    dic[zt(temp.s)] = 1;

    int head = 1, tail = 1;

    dl[1] = temp;

    while (head <= tail)

    {

        abc now = dl[head++];

        int ss[15];

        rep1(i, 1, 9) ss[i] = now.s[i];

        int t = now.pos;

        //up

        if (t > 3)

        {

            int tt = t - 3;

            swap(ss[tt], ss[t]);

            int pc = zt(ss);

            if (!dic[pc])

            {

                rep1(i, 1, 9) temp1.s[i] = ss[i];

                temp1.pos = tt, temp1.pre = head - 1, temp1.ope = 2;

                dl[++tail] = temp1;

                dic[pc] = tail;

            }

            swap(ss[tt], ss[t]);

        }

        //down

        if (t<7)

        {

            int tt = t + 3;

            swap(ss[tt], ss[t]);

            int pc = zt(ss);

            if (!dic[pc])

            {

                rep1(i, 1, 9) temp1.s[i] = ss[i];

                temp1.pos = tt, temp1.pre = head - 1, temp1.ope = 1;

                dic[pc] = tail+1;

                dl[++tail] = temp1;

            }

            swap(ss[tt], ss[t]);

        }

        //left

        if ((t % 3) != 1)

        {

            int tt = t - 1;

            swap(ss[tt], ss[t]);

            int pc = zt(ss);

            if (!dic[pc])

            {

                rep1(i, 1, 9) temp1.s[i] = ss[i];

                temp1.pos = tt, temp1.pre = head - 1, temp1.ope = 4;

                dic[pc] = tail+1;

                dl[++tail] = temp1;

            }

            swap(ss[tt], ss[t]);

        }

        //right

        if ((t % 3) != 0)

        {

            int tt = t + 1;

            swap(ss[tt], ss[t]);

            int pc = zt(ss);

            if (!dic[pc])

            {

                rep1(i, 1, 9) temp1.s[i] = ss[i];

                temp1.pos = tt, temp1.pre = head - 1, temp1.ope = 3;

                dic[pc] = tail+1;

                dl[++tail] = temp1;

            }

            swap(ss[tt], ss[t]);

        }

    }

}

void pri(int now){

    if (now == 1) return;

    int ju = dl[now].ope;

    if (ju == 1) printf("u");

    if (ju == 2) printf("d");

    if (ju == 3) printf("l");

    if (ju == 4) printf("r");

    pri(dl[now].pre);

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    bfs();

    while (getline(cin,t)){

        int num = 0;

        int len = t.size();

        rep1(i,0,len-1)

        {

            if (t[i]=='x') t[i] = '9';

            if (t[i]>='0' && t[i]<='9') ts[++num] = t[i]-'0';

            if (num==9) break;

        }

        int pc=dic[zt(ts)];

        if (pc){

            pri(pc);

            puts("");

        }

        else

            puts("unsolvable");

    }

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}