学步园

#include <iostream>
#include <queue>
#include <string>

using namespace std;

#define ROW 0
#define COL 1

#define U 1
#define R 2
#define D 3
#define L 0

struct Point
{
    short x;
    short y;
};

Point position[10] = {
    {0,0},
    {0,0}, //'1'
    {0,1},//'2'
    {0,2},//'3'
    {1,0},//'4'
    {1,1},//'5'
    {1,2},//'6'
    {2,0},//'7'
    {2,1},//'8'
    {2,2},//'x'
};

short dir[4][2] = {
    {-1, 0},
    {0, 1},
    {1, 0},
    {0, -1}
                  };


struct Node
{
    long cost;
    Point pos;
    short state;
    short dir;
    int hase;
    short step;
    char cArr[3][3];
    struct Node * pPre;

    bool friend operator < (const struct Node & a, const struct Node & b)
    {
        return a.cost > b.cost;
    }
} sta, save[370000];

priority_queue<Node> Open;

bool bVit[370000];
unsigned int sv = 0;

int Fn[10] = {1,1,2,6,24,120,720,5040,40320,362880};

bool resolve = false;


void Input()
{
    for (int i = 1; i < 3; ++i)
    {
        cin >> sta.cArr[0][i];
        if (sta.cArr[0][i] == 'x') sta.pos.x = 0, sta.pos.y = i;
    }
    for (int i = 1; i < 3; ++i)
      for (int j = 0; j < 3; ++j)
    {
        cin >> sta.cArr[i][j];
        if (sta.cArr[i][j] == 'x') sta.pos.x = i, sta.pos.y = j;
    }
}

inline int Hase()
{
    int i,j,k=0,ret=0,num=0;
    int b[10];
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
        {
            if (sta.cArr[i][j] == 'x')
              b[k++] = 9;
            else
              b[k++] = sta.cArr[i][j] - '0';
        }
    for(i=0;i<9;i++)
    {
       num=0;
       for(j=0;j<i;j++)
       {
           if(b[j]>b[i])  num++;
        }
          ret+=Fn[i] * num;
     }
     return ret;
//    int i,j,k,mark[10],sum=0,b[10];
//    k=0;
//    for(i=0;i<3;i++)
//        for(j=0;j<3;j++)
//        {
//            if (sta.cArr[i][j] == 'x')
//              b[k++] = 0;
//            else
//              b[k++] = sta.cArr[i][j] - '0';
//        }
//    memset(mark,0,sizeof(mark));
//    for(i=0;i<9;i++)
//    {
//        int t=b[i]-1;
//        int tmp=t;       
//        for(j=0;j<=tmp;j++)if(mark[j])t--;
//        mark[b[i]]=1;
//        sum+=Fn[i]*t;
//    }
//    return sum;
}

void F();

void Init()
{
    Input();
    resolve = false;
    sta.pPre = NULL;
    sta.state = -1;
    sta.step = 0;
    sta.hase = Hase();
    sta.dir = -1;
    F();

    sv = 0;
    memset(bVit, false, sizeof(bVit));
    memset(save, 0, sizeof(save));
}


inline int ManHaDom()
{
    int t = 0;
    for (int i = 0; i < 3; ++i)
     for (int j = 0; j < 3; ++j)
     { 
         short it = 0;
         if (sta.cArr[i][j] == 'x') continue;//it = 9;
         else it = sta.cArr[i][j] - '0';
         t += ( abs(position[it].x - i) + abs(position[it].y - j) );
     }
     if (t == 0)
         resolve = true;
     return t;
}

inline void F()
{
    sta.cost = ManHaDom();// + sta.step;
}

int CanSolve()
{
    int i,j,k=0,b[10],ret=0,num=0;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
        {
            if(sta.cArr[i][j] != 'x')
                b[k++]=sta.cArr[i][j] - '0';
        }
        for(i=0;i<8;i++)
        {
            num=0;
            for(j=0;j<i;j++)
                if(b[j]>b[i])  
                    num++;
                ret+=num;
        }
        return ret;
}

bool Astar()
{
    if (CanSolve() % 2 != 0) return false;
    memset(bVit, false, sizeof(bVit));
    while (!Open.empty()) Open.pop();
    Open.push(sta);
    bVit[sta.hase] = true;
    if (resolve) 
        return true;
    while (!Open.empty())
    {
        Node cur = Open.top();
        Open.pop();
        save[sv++] = cur;
        for (short i = 0; i < 4; ++i)
        {
            sta = cur;
            sta.pos.x = cur.pos.x + dir[i][ROW];
            sta.pos.y = cur.pos.y + dir[i][COL];
            if (sta.pos.x < 0 || sta.pos.x > 2 || sta.pos.y < 0 || sta.pos.y > 2) continue;

            swap(sta.cArr[cur.pos.x][cur.pos.y],sta.cArr[sta.pos.x][sta.pos.y]);

            sta.hase = Hase();
            if (bVit[sta.hase]) continue;

            bVit[sta.hase] = true;

            sta.step = cur.step + 1;
            F();
            sta.dir = i;
            sta.pPre = &save[sv - 1];
            Open.push(sta);
            if (resolve) 
                return true;
            //cout << Open.size() << endl;
        }
    }
    return false;
}

void PrintPath()
{
    if (resolve)
    {
        string str = "";
        do 
        {
            switch(sta.dir)
            {
            case U: str += 'r'; break;
            case L: str += 'u'; break;
            case R: str += 'd'; break;
            case D: str += 'l'; break;
            }
            if (sta.pPre == NULL) break;
            sta = *sta.pPre;
        }while (sta.dir != -1);
        reverse(str.begin(), str.end());
        cout << str << endl;
    }
    else
    {
        cout << "unsolvable\n";
    }

}

int main(int argv, char * args[])
{
    char c;
    while (cin >> c)
    {
        sta.cArr[0][0] = c;
        if (c == 'x') 
        {
            sta.pos.x = 0, sta.pos.y = 0;
        }
        Init();
        Astar();
        PrintPath();
    }
    return 0;
}