BOJ. Hide and Seek (1697)

Approach

Treat each integer from 0 through 100000 as a state. From a state x, one move reaches x - 1, x + 1, or 2 * x, whenever that result is within the allowed range. Each edge therefore has cost one, so breadth-first search visits states in nondecreasing distance from the start. The first time the target is reached is its shortest travel time.

The distance array also marks visited states: -1 means unseen. Each state is enqueued at most once, so the search takes O(100000) time and O(100000) space.

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 MAX = 100000;

    public static void main(String[] args) throws IOException {
        StringTokenizer input = new StringTokenizer(
                new BufferedReader(new InputStreamReader(System.in)).readLine());
        int start = Integer.parseInt(input.nextToken());
        int target = Integer.parseInt(input.nextToken());
        if (start == target) {
            System.out.println(0);
            return;
        }

        int[] distance = new int[MAX + 1];
        Arrays.fill(distance, -1);
        int[] queue = new int[MAX + 1];
        int head = 0;
        int tail = 0;

        distance[start] = 0;
        queue[tail++] = start;

        while (head < tail) {
            int current = queue[head++];
            int nextDistance = distance[current] + 1;

            if (current - 1 >= 0 && distance[current - 1] == -1) {
                if (current - 1 == target) {
                    System.out.println(nextDistance);
                    return;
                }
                distance[current - 1] = nextDistance;
                queue[tail++] = current - 1;
            }
            if (current + 1 <= MAX && distance[current + 1] == -1) {
                if (current + 1 == target) {
                    System.out.println(nextDistance);
                    return;
                }
                distance[current + 1] = nextDistance;
                queue[tail++] = current + 1;
            }
            if (current * 2 <= MAX && distance[current * 2] == -1) {
                if (current * 2 == target) {
                    System.out.println(nextDistance);
                    return;
                }
                distance[current * 2] = nextDistance;
                queue[tail++] = current * 2;
            }
        }
    }
}