#include <cmath> #include <ctime> #include <cctype> #include <climits> #include <cstdio> #include <cstdlib> #include <cstring> #include <map> #include <set> #include <queue> #include <stack> #include <string> #include <vector> #include <sstream> #include <iostream> #include <algorithm> #define INF (INT_MAX / 10) #define clr(arr, val) memset(arr, val, sizeof(arr)) #define pb push_back #define sz(a) ((int)(a).size()) using namespace std; typedef set<int> si; typedef vector<int> vi; typedef map<int, int> mii; typedef pair<int, int> pii; typedef long long ll; const double esp = 1e-5; #define M 400000 int orilen; int oritmp[9]; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; char mm[] = "urdl"; int goal[9] = {1, 2, 3, 4, 5, 6, 7, 8, 0}; char strtmp[20]; int fac[20], vis[2][M]; int st[2][M][9]; int head[2]; int tail[2]; int fa[2][M]; char direct[2][M]; int getcode(int s[]) { int res = 0; for (int i = 0; i < 9; ++i) { int cnt = 0; for (int j = i + 1; j < 9; ++j) { if (s[i] > s[j]) { ++cnt; } } res += cnt * fac[8 - i]; } return res; } // 忽略0之后,不改变排列的奇偶性 int check(int s[]) { int num = 0; for (int i = 0; i < 9; ++i) { if (s[i] == 0) { continue; } for (int j = i + 1; j < 9; ++j) { if (s[j] != 0 && s[i] > s[j]) { ++num; } } } return num % 2; } void dbfs(void) { head[0] = 1; head[1] = 1; tail[0] = 2; tail[1] = 2; clr(vis, 0); memcpy(st[0][1], oritmp, sizeof(oritmp)); memcpy(st[1][1], goal, sizeof(goal)); fa[0][1] = -1; fa[1][1] = -1; direct[0][1] = '*'; direct[1][1] = '*'; int code0 = getcode(st[0][1]); int code1 = getcode(st[1][1]); vis[0][code0] = 1; vis[1][code1] = 1; while (head[0] < tail[0] && head[1] < tail[1]) { int no = 0; if (head[0] == tail[0]) { no = 1; } else if (head[1] == tail[1]) { no = 0; } else { if (tail[0] - head[0] < tail[1] - head[1]) { no = 0; } else { no = 1; } } int ono = 1 - no; int code = getcode(st[no][head[no]]); //printf("\n%d..%d", code, no); for (int i = 0; i < 9; ++i) { if (i % 3 == 0) { //printf("\n"); } //printf("%d ", st[no][head[no]][i]); } if (vis[ono][code]) { //printf("done\n"); string ans; int pos = head[no]; if (no) { for (int i = 0; i < tail[0]; ++i) { int tmp = getcode(st[0][i]); if (tmp == code) { pos = i; break; } } } else { pos = head[no]; } int p = pos; //printf("\n%d.....\n", pos); while (fa[0][p] != -1) { ans += direct[0][p]; p = fa[0][p]; } reverse(ans.begin(), ans.end()); //cout << ans << endl; if (no == 0) { for (int i = 0; i < tail[1]; ++i) { int tmp = getcode(st[1][i]); if (tmp == code) { pos = i; break; } } } else { pos = head[no]; } p = pos; //printf("%d.....%d\n", pos, head[no]); while (fa[1][p] != -1) { ans += direct[1][p]; p = fa[1][p]; } printf("%s\n", ans.c_str()); return; } int idx = 0; for (int i = 0; i < 9; ++i) { if (st[no][head[no]][i] == 0) { idx = i; break; } } int x = idx / 3; int y = idx % 3; for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; int nidx = nx * 3 + ny; if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) { memcpy(st[no][tail[no]], st[no][head[no]], sizeof(st[no][head[no]])); swap(st[no][tail[no]][idx], st[no][tail[no]][nidx]); int ncode = getcode(st[no][tail[no]]); if (!vis[no][ncode]) { vis[no][ncode] = 1; fa[no][tail[no]] = head[no]; direct[no][tail[no]] = mm[no ? (i + 2) % 4 : i]; ++tail[no]; } } } ++head[no]; } printf("unsolvable\n"); } int main(int argc, char *argv[]) { fac[0] = 1; for (int i = 1; i < 20; ++i) { fac[i] = fac[i - 1] * i; } while (fgets(strtmp, 20, stdin) != NULL) { //printf("fgets\n"); int len = strlen(strtmp); orilen = 0; for (int i = 0; i < len; ++i) { if (isdigit(strtmp[i])) { oritmp[orilen++] = strtmp[i] - '0'; } else if (strtmp[i] == 'x') { oritmp[orilen++] = 0; } } for (int i = 0; i < 9; ++i) { if (i % 3 == 0) { //printf("\n"); } //printf("%d ", oritmp[i]); } //printf("\n"); //printf("%d\n", getcode(oritmp)); if (check(oritmp)) { printf("unsolvable\n"); continue; } dbfs(); } return 0; } /************************************************************** Problem: 2352 User: admin Language: C++ Result: Wrong Answer ****************************************************************/