https://www.acmicpc.net/problem/1963

1963.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static final int SIZE = 10000;
	static int dist[] = new int[SIZE];
	static boolean isNotPrime[] = new boolean[SIZE];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		eratosthenes();

		for (int n = Integer.parseInt(br.readLine()); n > 0; n--) {
			String lines[] = br.readLine().split(" ");

			int start = Integer.parseInt(lines[0]);
			int target = Integer.parseInt(lines[1]);

			System.out.println(bfs(start, target));
		}

		br.close();
	}

	private static void eratosthenes() {
		for (int i = 2; i * i < SIZE; i++) {
			if (!isNotPrime[i]) {
				for (int j = i * i; j < SIZE; j += i) {
					isNotPrime[j] = true;
				}
			}
		}
		isNotPrime[1] = true;
	}

	private static String bfs(int start, int target) {
		int min = 0x3f3f3f3f;
		Arrays.fill(dist, 0x3f3f3f3f);

		Queue<Integer> q = new LinkedList<>();

		q.offer(start);
		dist[start] = 0;

		while (!q.isEmpty()) {
			int curPos = q.poll();
			int curDist = dist[curPos];

			if (curPos == target) {
				min = Math.min(min, curDist);
			}

			String sPos = "" + curPos;

			for (int i = 0; i < 4; i++) {
				for (int j = (i == 0 ? 1 : 0); j < 10; j++) {
					int nextPos = getNextPos(sPos, i, j);
					int nextDist = curDist + 1;

					if (shouldMove(nextPos, nextDist)) {
						q.offer(nextPos);
						dist[nextPos] = nextDist;
					}
				}
			}
		}

		return min == 0x3f3f3f3f ? "Impossible" : "" + min;
	}

	private static int getNextPos(String str, int idx, int num) {
		return Integer.parseInt(str.substring(0, idx) + num + str.substring(idx + 1));
	}

	private static boolean shouldMove(int nextPos, int nextDist) {
		return !isNotPrime[nextPos] && nextDist < dist[nextPos];
	}
}