アルゴリズム::白準::BFS::13913::かくれんぼ4

質問する

質問へのアクセス

問題を理解する

コード#コード#

#include <iostream>
#include <vector>
#include <queue>
#define MAX 100001
using namespace std;

int N, K, track[MAX];
bool visited[MAX];

// 재귀여도 최대 20~30번 돌기 때문에 빠릅니다.
void traceTrack(int s, int e) {
	if (s != e) traceTrack(s, track[e]);
	cout << e << ' ';
}

void solve() {
	queue<pair<int, int>> q;
	q.push({N, 0});
	visited[N] = true;
	
	int ans = 0;
	while (!q.empty()) {
		int cPos = q.front().first, cSec = q.front().second;
		if (cPos == K){ ans = cSec; break; }
		q.pop();
		int nPos1 = cPos * 2, nPos2 = cPos - 1, nPos3 = cPos + 1, nSec = cSec + 1;
		if (nPos1 < MAX && !visited[nPos1])
			q.push({nPos1, nSec}), visited[nPos1] = true, track[nPos1] = cPos;
		if (nPos2 >= 0 && !visited[nPos2])
			q.push({nPos2, nSec}), visited[nPos2] = true, track[nPos2] = cPos;
        if (nPos3 < MAX && !visited[nPos3])
        	q.push({nPos3, nSec}), visited[nPos3] = true, track[nPos3] = cPos;
    }
    cout << ans << '\n';
    traceTrack(N, K);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> K;
	if (N > K) {
		cout << N - K << '\n';
		for (int i = N; i >= K; --i) cout << i << ' ';
		return 0;
	}
	solve();
}

結果