#include #include #include using std::priority_queue; #define ABS(x) ((x) < 0 ? -(x) : (x)) const int dst = 123456780; const int S = 362880; const int frac[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; int perm2no(int p) { if (p < 0) return -1; char perm[10]; sprintf(perm, "%09d", p); bool used[9] = {}; int n = 0; for (int i = 0; i < 9; i++) { for (int j = perm[i] - '1'; 0 <= j; j--) { if (used[j]) continue; n += frac[8 - i]; } used[perm[i] - '0'] = true; } return n; } int no2perm(int n) { char perm[10]; bool used[9] = {}; for (int i = 0; i < 9; i++) { int j = n / frac[8 - i]; n %= frac[8 - i]; for (int k = 0; k < 9; k++) { if (used[k]) continue; if (j-- == 0) { used[k] = true; perm[i] = k + '0'; break; } } } return atoi(perm); } int next_state(int p, char m) { char perm[10]; sprintf(perm, "%09d", p); int i = 0; while (perm[i] != '0') i++; switch (m) { case 'u': if (i < 3) return -1; perm[i] = perm[i - 3]; perm[i - 3] = '0'; return atoi(perm); case 'd': if (8 < i + 3) return -1; perm[i] = perm[i + 3]; perm[i + 3] = '0'; return atoi(perm); case 'l': if (i % 3 == 0) return -1; perm[i] = perm[i - 1]; perm[i - 1] = '0'; return atoi(perm); case 'r': if (i % 3 == 2) return -1; perm[i] = perm[i + 1]; perm[i + 1] = '0'; return atoi(perm); } return -1; } bool even_perm(int s) { char perm[10]; sprintf(perm, "%09d", s); int cnt = 0; // 0 is not included for (int i = 1; i < 9; i++) { if (perm[i] == '0') continue; for (int j = 0; j < i; j++) if (perm[i] < perm[j]) cnt++; } return cnt % 2 == 0; } struct Node { int s; int p; int f; int g; char m; Node(int s = 0, int p = 0, int f = 0, int g = 0, char m = 0) : s(s), p(p), f(f), g(g), m(m) {} bool operator<(const Node &that) const { return that.f < this->f; } } close[S]; char moves[] = "udlr"; char res[S + 1]; int eval_h(int s) { int res = 0; for (int i = 8; 0 <= i; i--) { int c = s % 10; if (c != 0) { int x = (c - 1) / 3; int y = (c - 1) % 3; int cx = i / 3; int cy = i % 3; res += ABS(cx - x) + ABS(cy - y); } s /= 10; } return res; } bool a_star(int s) { if (!even_perm(s)) return false; int no = perm2no(s); close[no] = Node(s, -1); priority_queue pq; pq.push(close[no]); while (!pq.empty()) { Node cur = pq.top(); pq.pop(); if (cur.s == dst) return true; for (int i = 0; i < 4; i++) { char m = moves[i]; int nxt = next_state(cur.s, m); no = perm2no(nxt); if (no == -1 || close[no].s != 0) continue; int h = eval_h(nxt); close[no] = Node(nxt, cur.s, cur.g + 1 + h, cur.g + 1, m); pq.push(close[no]); } } return false; } int main() { char perm[10]; for (int i = 0; i < 9; i++) { scanf("%s", &perm[i]); if (perm[i] == 'x') perm[i] = '0'; } int src = atoi(perm); if (a_star(src)) { int pos = perm2no(dst), i = 0; do { res[i++] = close[pos].m; pos = perm2no(close[pos].p); } while (pos != -1); // The (i-1)th char is 0! So i - 2 for (int j = i - 2; 0 <= j; j--) printf("%c", res[j]); printf("\n"); } else { printf("unsolvable\n"); } return 0; }