BOJ 13913:鬼ごっこ4

✔問題リンク

✔トラブルシューティングポリシー

✔解決過程

✔正解コード

#include <bits/stdc++.h>
using namespace std;

int dist[100002];
int before[100002];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    queue < int > q;
    cin >> n >> k;

    fill(dist, dist + 100001, -1);
    fill(before, before + 100001, -1); // new
    dist[n] = 0;
    q.push(n);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        for (int new_: {
                cur - 1,
                cur + 1,
                2 * cur
            }) {
            if (new_ < 0 || new_ > 100000) continue;
            if (dist[new_] != -1) continue;
            dist[new_] = dist[cur] + 1;
            q.push(new_);
            before[new_] = cur; // new
        }
    }

    vector < int > route;
    int now = k;
    while (now != n) {
        route.push_back(now);
        now = before[now];
    }
    route.push_back(now); // push back n
    reverse(route.begin(), route.end());
    cout << dist[k] << '\n';

    for (int i: route) cout << i << " ";

}

✔ Comment