#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<cmath>#include<queue>#include<map>#include<algorithm>#define mx 4000000using namespace std;struct chess{    int node[9];    int step;    int pos;    bool cla;};int chart = 0,step[2][10000];map<int,int> trans[2];chess start,end;bool jud[2][mx];int m_jud[9][4] = {1,3,-1,-1,                   0,4,2,-1,                   1,5,-1,-1,                   0,4,6,-1,                   1,3,5,7,                   2,4,8,-1,                   3,7,-1,-1,                   4,6,8,-1,                   5,7,-1,-1};int getval(chess x){    int res = 1,val = 0;    for(int i = 1;i <= 9;i++){        val += res * x.node[i-1];        res *= (i+1);    }    return val;}void putout(chess pt){    cout<<"the class:"<<pt.cla<<endl;    for(int i = 1;i <= 3;i++){        for(int j = 1;j <= 3;j++){            cout<<pt.node[(i-1) * 3 + j - 1] <<" ";        }        cout<<endl;    }    cout<<"steps: "<<pt.step<<" , pos: "<<pt.pos<<endl;}void init(){    int co,md = 1;    cin>>co;    for(int i = 8;i >= 0;i--){        start.node[i] = (co / md)% 10;        md *= 10;        if(start.node[i] == 0) start.pos = i;            }    start.cla = 0;    end.node[0] = 1;    end.node[1] = 2;    end.node[2] = 3;    end.node[3] = 8;    end.node[4] = 0;    end.node[5] = 4;    end.node[6] = 7;    end.node[7] = 6;    end.node[8] = 5;    end.step = start.step = 0;    end.pos = 4;    end.cla = 1;}void bfs(){    queue<chess> now,then;    now.push(start);    now.push(end);    chess test,h;    int p,code;    while(!now.empty()){        h = now.front();        p = h.pos;        code = getval(h);        trans[h.cla][code] = chart;        step[h.cla][chart] = h.step;        chart++;        jud[h.cla][code] = 1;        for(int i = 0,j = m_jud[p][i];j != -1 && i <= 3;i++,j = m_jud[p][i]){            test = h;            test.step++;            swap(test.node[p],test.node[j]);            code = getval(test);            //if(jud[test.cla][code]) continue;            test.pos = j;            trans[test.cla][code] = chart;            step[test.cla][chart] = test.step;            chart++;            if(jud[!test.cla][code]){                cout<<step[0][trans[0][code]] + step[1][trans[1][code]]<<endl;                return;            }            if(!jud[test.cla][code]){                now.push(test);                jud[test.cla][code] = 1;            }                    }        now.pop();    }}int main(){    init();        bfs();    return 0;}

#include <iostream>#include <cmath>#include <cstdlib>#include <cstdio>#include <cstring>using namespace std;const unsigned int M = 1001;int dir[4][2] = {    1, 0, // Down    -1, 0, // Up    0,-1, // Left    0, 1 // Right};typedef struct STATUS{    int arr[3][3];    int r,c;}STATUS;char dirCode[] = {"dulr"};char rDirCode[] = {"udrl"};char path[M]; // 最优解STATUS begin, end = { 1,2,3,4,5,6,7,8,0,2,2 }; // 起始和终止状态int maxDepth = 0; // 深度边界int diff(const STATUS &cur) // 启发函数{    int i,j,k,m,ans=0;    for(i=0;i<=2;i++)        for(j=0;j<=2;j++)        {            if(cur.arr[i][j] != 0)            {                for(k=0;k<=2;k++)                    for(m=0;m<=2;m++)                    {                        if(cur.arr[i][j] == end.arr[k][m])                        {                            ans+=abs(i-k)+abs(j-m);                            break;                        }                    }            }        }    return ans;}bool dfs(STATUS &cur, int depth, int h, char preDir){    if(memcmp(&cur, &end, sizeof(STATUS)) == 0 )    { // OK找到解了:)        path[depth] = ‘/0‘;        return true;    }    if( depth + h > maxDepth ) return false; // 剪枝    STATUS nxt; // 下一状态    for(int i=0; i<4; i++)    {        if(dirCode[i]==preDir) continue; // 回到上次状态,剪枝        nxt = cur;        nxt.r = cur.r + dir[i][0];        nxt.c = cur.c + dir[i][1];        if( !( nxt.r >= 0 && nxt.r < 3 && nxt.c >= 0 && nxt.c < 3 ) )            continue;        int nxth = h;        int preLen,Len,desNum=cur.arr[nxt.r][nxt.c],desR=(desNum-1)/3,desC=(desNum-1)%3;        preLen=abs(nxt.r-desR)+abs(nxt.c-desC);        Len=abs(cur.r-desR)+abs(cur.c-desC);        nxth = h - preLen + Len;        swap(nxt.arr[cur.r][cur.c], nxt.arr[nxt.r][nxt.c]);        path[depth] = dirCode[i];        if(dfs(nxt, depth + 1, nxth, rDirCode[i]))            return true;    }    return false;}int IDAstar(){    int nh = diff(begin);    maxDepth = nh;    while (!dfs(begin, 0, nh, ‘/0‘))        maxDepth++;    return maxDepth;}void Input(){    char ch;    int i, j;    for(i=0; i < 3; i++){        for(j=0; j < 3; j++){            do{                scanf("%c", &ch);            }            while( !( ( ch >= ‘1‘ && ch <= ‘8‘ ) || ( ch == ‘x‘ ) ) )                 ;            if( ch == ‘x‘ ) {                begin.arr[i][j] = 0;                begin.r = i;                begin.c = j;            }            else                begin.arr[i][j] = ch - ‘0‘;        }    }}bool IsSolvable(const STATUS &cur){    int i, j, k=0, s = 0;    int a[8];    for(i=0; i < 3; i++){        for(j=0; j < 3; j++){            if(cur.arr[i][j]==0) continue;            a[k++] = cur.arr[i][j];        }    }    for(i=0; i < 8; i++){        for(j=i+1; j < 8; j++){            if(a[j] < a[i])                s++;        }    }    return (s%2 == 0);}int main(){    Input();    if(IsSolvable(begin)){        IDAstar();        printf("%s/n", path);    }    else        printf("unsolvable/n");    return 0;}