BOJ. DSLR (9019)

Approach

Treat each integer from 0 through 9999 as a vertex in a directed graph. Each of the four DSLR commands is an edge from the current value to the value produced by that command. Since every command costs one step, breadth-first search (BFS) explores states in nondecreasing order of the number of commands from the start.

Visit outgoing edges in D, S, L, R order. BFS then discovers shortest paths first and orders equal-length paths by that required command priority. Mark a state visited when it is enqueued; its first parent and command therefore record the highest-priority shortest path to it. Each of the 10,000 states is enqueued at most once. Store only integer states in the queue, and reconstruct the answer by following parent links backward. If the start already equals the target, the reconstructed path has length zero, so the output is an empty line.

Each state has four outgoing transitions, giving O(10,000) time and O(10,000) auxiliary space per test case.

Problem link

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static final int STATE_COUNT = 10000;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(reader.readLine());
        StringBuilder output = new StringBuilder();

        for (int testCase = 0; testCase < testCases; testCase++) {
            StringTokenizer input = new StringTokenizer(reader.readLine());
            int start = Integer.parseInt(input.nextToken());
            int target = Integer.parseInt(input.nextToken());

            int[] parent = new int[STATE_COUNT];
            Arrays.fill(parent, -1);
            char[] commandUsed = new char[STATE_COUNT];
            int[] queue = new int[STATE_COUNT];
            int head = 0;
            int tail = 0;

            parent[start] = start;
            queue[tail++] = start;

            while (head < tail && parent[target] == -1) {
                int current = queue[head++];

                int next = current * 2 % STATE_COUNT;
                if (parent[next] == -1) {
                    parent[next] = current;
                    commandUsed[next] = 'D';
                    queue[tail++] = next;
                }

                next = current == 0 ? 9999 : current - 1;
                if (parent[next] == -1) {
                    parent[next] = current;
                    commandUsed[next] = 'S';
                    queue[tail++] = next;
                }

                next = current % 1000 * 10 + current / 1000;
                if (parent[next] == -1) {
                    parent[next] = current;
                    commandUsed[next] = 'L';
                    queue[tail++] = next;
                }

                next = current % 10 * 1000 + current / 10;
                if (parent[next] == -1) {
                    parent[next] = current;
                    commandUsed[next] = 'R';
                    queue[tail++] = next;
                }
            }

            char[] reversedPath = new char[STATE_COUNT];
            int pathLength = 0;
            for (int state = target; state != start; state = parent[state]) {
                reversedPath[pathLength++] = commandUsed[state];
            }
            for (int i = pathLength - 1; i >= 0; i--) {
                output.append(reversedPath[i]);
            }
            output.append('\n');
        }

        System.out.print(output);
    }
}