#include <iostream>#include <stack>#include <math.h>#include <stdio.h>#include <string.h>#include <stdlib.h>using namespace std;const int maxn = 10;char ans[100];int tot, dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};struct Node{ char map[maxn]; int g, move, xpos;}starts;void init(){ for (int i = 0; i < 9; i++) { starts.map[i] = ' '; while (starts.map[i] == ' ') scanf("%c",&starts.map[i]); if (starts.map[i] == 'x') { starts.map[i] = 9; starts.xpos = i; } else starts.map[i] -= '0'; }}int h(Node &a){ int x1, x2, y1, y2, i, r = 0; for (i = 0; i < 9; i++) { x1 = i / 3; y1 = i % 3; x2 = (a.map[i] - 1) / 3; y2 = (a.map[i] - 1) % 3; r += abs(x1 - x2) + abs(y1 - y2); } return r;}Node getchild(int a, Node ¤ts){ int x, y, pos, i; Node r; x = currents.xpos / 3 + dir[a][0]; y = currents.xpos % 3 + dir[a][1]; r.xpos = -1; if (x < 0 || y < 0 || x > 2 || y > 2) return r; pos = x * 3 + y; r.xpos = pos; r.g = currents.g + 1; r.move = a; for (i = 0; i < 9; i++) r.map[i] = currents.map[i]; r.map[pos] = 9; r.map[currents.xpos] = currents.map[pos]; return r;}bool ida(){ int pathlimit, i, temp, next; bool success = 0; Node currents, child; next = h(starts)/2; stack<Node> stk; do { pathlimit = next; if (pathlimit > 100) return false; tot = 0; starts.g = 0; starts.move = -1; next = 200; stk.push(starts); do { currents = stk.top(); ans[currents.g] = currents.move; stk.pop(); temp = h(currents); if (temp == 0) { tot = currents.g; success = true; } else if (pathlimit >= currents.g + temp / 2) { for (i = 0; i < 4; i++) { child = getchild(i, currents); if (child.xpos != -1 && abs(child.move - currents.move) != 2) stk.push(child); } }else if (next > currents.g + temp / 2) next = currents.g + temp / 2; }while (!success && !stk.empty()); }while (!success); return true;}void print(){ int i; for (i = 1; i <= tot; i++) switch(ans[i]) { case 0: printf("u"); break; case 1: printf("r"); break; case 2: printf("d"); break; case 3: printf("l"); break; } printf("n");}int main(){ init(); if (ida()) print(); else printf("unsolvablen"); return 0;}
