9019

[geonnho0]

문제 링크

[geonnho0]

코드

public class Main {

    static Queue<Integer> queue;
    static String[] commands;
    static int target;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            String[] line = br.readLine().split(" ");
            int A = Integer.parseInt(line[0]);
            target = Integer.parseInt(line[1]);
            bfs(A);
        }
    }

    static void bfs(int start) {
        queue = new LinkedList<>();
        commands = new String[10000];
        queue.offer(start);
        commands[start] = "";

        while (!queue.isEmpty()) {
            int curr = queue.poll();

            if (check(curr, D(curr), "D"))
                return;
            if (check(curr, S(curr), "S"))
                return;
            if (check(curr, L(curr), "L"))
                return;
            if (check(curr, R(curr), "R"))
                return;
        }
    }

    static boolean check(int curr, int next, String command) {
        if (next == target) {
            System.out.println(commands[curr] + command);
            return true;
        }
        if (commands[next] == null) {
            commands[next] = commands[curr] + command;
            queue.offer(next);
        }
        return false;
    }

    static int D(int n) {
        return (n * 2) % 10000;
    }

    static int S(int n) {
        return n - 1 < 0 ? 9999 : n - 1;
    }

    static int L(int n) {
        return (n % 1000) * 10 + (n / 1000);
    }

    static int R(int n) {
        return (n % 10) * 1000 + (n / 10);
    }

}