import java.util.ArrayList;
public class GenericTest {
	public enum Direction {
		//0 表示上， 1 表示下， 2表示左，3表示右
		U, D, L, R
	}
	public static class Node {
		public String current;
		public Direction direction;
		public int pos;
		public Node (String c, Direction d, int p) {
			current = c;
			direction = d;
			pos = p;
		}
	}
	static String des = "0212212112122121";
	public static void main(String[] argv) {
		String src = "0122112211221122";
		Node first = new Node(src, null, 0);
		candidates.add(first);
		srcToDes(0, 1);
	}
	public static ArrayList<Node> candidates = new ArrayList(80000);
	public static String exchangeChar(String src, int current, int next) {
		//System.out.println("exchange "+ current + " with " + next);
		char[] temp = src.toCharArray();
		temp[current] = temp[next];
		temp[next] = '0';
		return String.copyValueOf(temp);
	}
	public static boolean isInCandidates(String test) {
	   for (Node t : candidates) {
		   if (t.current.equals(test)) {
			   return true;
		   }
	   }
		return false;
	}
	public static void printPath(int i, Direction m) {
		StringBuilder sb = new StringBuilder(50);
		sb.append(m.name());
		while (i != 0) {
			Node t = candidates.get(i);
			System.out.println("pos:" + t.current + "direction:" + t.direction);
			sb.insert(0,t.direction.name().charAt(0));
			i = t.pos;
		}
		System.out.println("result:" + sb.toString());
	}
	public static void srcToDes(int start, int end) {
		System.out.println("start: " + start + " end: " + (end-1));
		for (int i = start; i < end; i++) {
			Node temp = candidates.get(i);
			String src = temp.current;
			int posCurrent = src.indexOf("0");
			if (1 <= posCurrent/4 && temp.direction != Direction.D) {
				//往上走
				int nextCurrent = posCurrent - 4;
				String up =exchangeChar(src, posCurrent, nextCurrent);
				if (up.equals(des)) {
					System.out.println("found!" + i);
					printPath(i, Direction.U);
					return ;
				}
				if(!isInCandidates(up)) {
					candidates.add(new Node(up,Direction.U,i));
				}
			}
			if (posCurrent/4 <= 2 && temp.direction != Direction.U) {
				//往下走
				int nextCurrent = posCurrent + 4;
				String down =exchangeChar(src, posCurrent, nextCurrent);
				if (down.equals(des)) {
					System.out.println("found!" + i);
					printPath(i, Direction.D);
					return ;
				}
				if(!isInCandidates(down)) {
					candidates.add(new Node(down, Direction.D,i));
				}
			}
			if (posCurrent%4 != 0 && temp.direction != Direction.R) {
				//往左走
				int nextCurrent = posCurrent - 1;
				String left =exchangeChar(src, posCurrent, nextCurrent);
				if (left.equals(des)) {
					System.out.println("found!" + i);
					printPath(i, Direction.L);
					return ;
				}
				if(!isInCandidates(left)) {
					candidates.add(new Node(left, Direction.L,i));
				}
			}
			if (posCurrent%4 != 3 && temp.direction != Direction.L) {
				//往右走
				int nextCurrent = posCurrent + 1;
				String right =exchangeChar(src, posCurrent, nextCurrent);
				if (right.equals(des)) {
					System.out.println("found!" + i);
					printPath(i, Direction.R);
					return ;
				}
				if(!isInCandidates(right)) {
					candidates.add(new Node(right, Direction.R,i));
				}
			}
		}
		srcToDes(end, candidates.size());
	}
}