伯準鬼ごっこ4(13913)

かくれんぼをする

1.ヒント

1)1つの点を頂点とし,移動を頂点間の幹線として定義する場合,この問題は最短経路の長さを探すことである.一部の問題をDPに分けて解決しようとすると,問題間に相互依存性が生じることは不可能である.

2)幹線の重み付けはいずれも1であるため,BFSを用いて最短経路の長さを求めることができる.しかし頂点の範囲は1≦x≦1051lexle 10^51≦x≦105ですか?

3）BFSプロセス中に隣接する頂点をチェックするたびに、その頂点にどの頂点から到達したかが保存される。頂点は一度しかアクセスしないので、以前の頂点は唯一です。KKKの最短経路が見つかった瞬間,それを逆方向に追跡し,実際の最短経路の1つを得ることができる.

2.近接

後ろから質問してもいいですか?

NNNからKNKへの最短パスを見つけるのは難しいですが、どの頂点からのパスを頂点ごとに保存しておけばKNKからNNNに戻るのは簡単なので、実際に最短パスを見つけることができます.
定点の範囲は何ですか.問題点で10510^5105を超えてはいけない制限はありませんが、いずれの場合も10510^5105を超えた位置に行ってしまうとベストな選択肢にはなりません.10510^5105を超える場合は2∺X 2*X 2∺Xに移行し、移行した場合はXͧX-1 Xͧ1に戻らなければならない.2∧X 2*X 2∧Xをする前に
X∮1 X-1 X∮1の方が良いので、頂点の範囲は1≦x≦1051lexle 10^51≦x≦105です.

3.実施

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();
	}
	
}

1）時間複雑度

2）テストケース