ARC 011C - ダブレット

問題

http://arc011.contest.atcoder.jp/tasks/arc011_3

解法

編集距離が1の単語間に辺を貼って幅優先探索した後, 経路復元します.

ソースコード

#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

using P_SI = pair<string, int>;

int main() {
    map<string, int> step;
    map<string, string> hist;   // 経路復元に使用

    string first, last;
    cin >> first >> last;

    hist[first] = first;

    step[last] = -1;
    hist[last] = last;

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        step[s] = -1;
        hist[s] = s;
    }

    queue<P_SI> que;
    que.push(make_pair(first, 0));
    step[first] = 0;

    // 幅優先探索
    while (!que.empty()) {
        P_SI st = que.front(); que.pop();
        string cur = st.first;
        int cost = st.second;

        for (auto mapping : step) {
            string next = mapping.first;
            int diff = 0;
            for (int i = 0; i < cur.size(); i++) {
                if (cur[i] != next[i]) diff++;
            }
            if (diff == 1 && step[next] < 0) {
                step[next] = cost + 1;
                hist[next] = cur;

                que.push(make_pair(next, cost + 1));
            }
        }
    }

    if (step[last] < 0) {
        cout << -1 << endl;
        return 0;
    }

    vector<string> history;
    history.push_back(last);

    string cur = hist[last];
    while (cur != first) {
        history.push_back(cur);
        cur = hist[cur];
    }
    history.push_back(cur);

    reverse(history.begin(), history.end());

    cout << history.size() - 2 << endl;
    for (string h : history) {
        cout << h << endl;
    }

    return 0;
}

感想

多分ARCのCの中でも簡単な方.