質問する

秀斌は弟と隠れん坊をしている.秀彬は現在点N(0≦N≦100000)、弟は点K(0≦K≦100000)にいる.スビンは歩いたり瞬時に移動したりすることができます秀彬の位置がXであれば、1秒後にX-1またはX+1に移動します.瞬間移動なら1秒後に2*Xの位置に移動します.
もし秀彬と弟の位置があれば、秀彬が弟を探す最も速い時間は数秒後であることを求めるプログラムを書きます.

入力

一行目はスビンのポジションNと弟のポジションKNとKは整数です.

しゅつりょく

秀彬が弟を探している一番速い時間を印刷します.

に答える

この問題はbfsで解決でき,以前の値+1の形式で解決できる.
最大10,000個の配列サイズを作成し、(x-1,x+1)、瞬時移動(x*2)したときに、配列の範囲外であるかどうかを確認し、bfsを実行します.
アクセス配列は移動時間を格納し,初期位置の値は0であり,出力時に[k]にアクセスできる.

ソース

import java.util.*;

public class Main {
	public static int n, k;

	// 해당 인덱스까지 걸린 시간
	public static int[] visited = new int[100001];

	public static void bfs(int x) {
		Queue<Integer> q = new LinkedList<>();

		q.offer(x);
		visited[x] = 0;

		while (!q.isEmpty()) {
			int now = q.poll();

			// 위치가 같을 경우
			if (now == k) {
				break;
			}

			// 걷기(x-1, x+1), 순간이동 (2*x)
			if (now + 1 <= 100000 && visited[now + 1] == 0) {
				q.offer(now + 1);
				visited[now + 1] = visited[now] + 1;
			}

			if (now - 1 >= 0 && visited[now - 1] == 0) {
				q.offer(now - 1);
				visited[now - 1] = visited[now] + 1;
			}

			if (now * 2 <= 100000 && visited[now * 2] == 0) {
				q.offer(now * 2);
				visited[now * 2] = visited[now] + 1;
			}

		}

		System.out.println(visited[k]);

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		k = sc.nextInt();

		bfs(n);

	}

}