에서 까지의 최단 경로를 실제로 찾아내는 것은 어렵지만 정점마다 어느 정점에서 왔는지를 저장 해 놓으면 에서 으로 돌아가는 것은 쉽기 때문에 최단 경로를 실제로 찾아낼 수 있다.
정점의 범위는 어떻게 될까? 문제에서 을 넘기면 안된다는 제약은 없지만 어떤 경우도 를 넘기는 위치를 갔다가 오면 최적해가 될 수 없다. 를 넘어가는 경우는 로 넘어가는 것인데 넘어가면 무조건 로 돌아와야 한다. 그럴 바에는 를 하기 전에
을 하는 것이 더 낫기 때문에 정점의 범위는 이 된다.
public class Main {
static int N; static int K;
// here에서 way번째 방법으로 도착하는 곳 반환
static int move(int here, int way) {
switch (way) {
case 0 : return here - 1;
case 1 : return here + 1;
case 2 : return 2 * here;
}
return -1;
}
static boolean inRange(int here) { return 0 <= here && here <= 100000; }
static void bfs() {
Queue<Integer> q = new LinkedList<>();
q.offer(N);
int[] dist = new int[200000];
Arrays.fill(dist, -1);
dist[N] = 0;
int[] parent = new int[200000];
Arrays.fill(parent, -1);
parent[N] = N;
while (!q.isEmpty() || parent[K] == -1) {
int here = q.poll();
for (int d = 0; d < 3; d++) {
int there = move(here, d);
if (!inRange(there) || dist[there] != -1) continue;
q.offer(there);
dist[there] = dist[here] + 1;
parent[there] = here;
}
}
System.out.println(dist[K]);
Stack<Integer> s = new Stack<>();
for (int p = K; p != N; p = parent[p])
s.push(p);
s.push(N);
StringBuilder ans = new StringBuilder();
while (!s.isEmpty()) ans.append(s.pop()).append(" ");
System.out.println(ans.toString().trim());
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
bfs();
}
}