開啟章節選單

10150 Doublets

題目連結

題目敘述

Doublets是一對單字，兩者恰好只有一個字母不同
例如 “booster” 與 “rooster”，或 “rooster” 與 “roaster”，或 “roaster” 與 “roasted”

給定一個最多包含 25143 個小寫單字的字典
每個單字長度不超過 16 個字母
接著，給定若干對單字
對於每一對單字
請找出一個最短的單字序列
該序列以第一個單字開始
以第二個單字結束
且序列中任意相鄰的兩個單字都是一對 雙字

例如，如果給定的輸入單字對是 “booster” 和 “roasted”
一種可能的解法為：
booster → rooster → roaster → roasted（假設這些單字都存在於字典中）。

輸入格式

輸入首先是一個字典，接著是若干對輸入單字。

  • 字典由若干單字構成，每行一個單字，以一個空行結束。
  • 接下來的每一行包含一對單字，兩者以空格分隔。

輸出格式

對於每一對輸入單字，輸出若干行：

  1. 從第一個單字開始，每一行輸出序列中的一個單字，直到最後一行為第二個單字。
  2. 序列中任意相鄰的兩行所代表的單字必須構成一對 Doublets。
  3. 如果存在多種最短解，輸出任意一種。
  4. 若不存在可行解，則輸出一行： 
    No solution.
  5. 不同測試用例之間輸出一個空行作為分隔。

解題思路

  1. 字典構建：將所有輸入的單字讀取至一個列表，作為圖的節點。
  2. 圖的構建：針對同長度的任意兩個單字，若僅有一個字母不同（Doublets 條件），則在兩者之間新增一條無向邊，形成鄰接表。
  3. BFS 搜索：對於每一對查詢的起點與終點單字，採用廣度優先搜尋（BFS）以找到最短轉換序列。
    • 使用一個佇列儲存待訪問節點，並以兩個 map 記錄已訪問狀態與前驅節點。
    • 當當前節點等於終點時，即可停止搜索，因為 BFS 保證首次到達即為最短路徑。
  4. 路徑重建：若存在可行解，根據前驅映射從終點回溯至起點，並反向輸出；若無解，則印出「No solution.」。
  5. 多組查詢：輸出結果之間以空行分隔。

程式碼

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

int main() {
    string s;
    vector<string> word;
    while (getline(cin, s), s != "") word.push_back(s); // 讀取整個字典：逐行讀入單字，直到遇到空行終止

    map<string, vector<string>> mp; // 構建鄰接表：mp[a] 存放與單字 a 僅有一字母差異的所有單字
    for (auto &a : word) for (auto &b : word) if (a.size() == b.size()) {
        int diff = 0;
        for (int i = 0; i < a.size() && diff < 2; i++) diff += a[i] != b[i]; // 計算兩單字之間的字母差異數量，差異超過 1 時提前終止
        if (diff == 1) mp[a].push_back(b); // 若僅差異一位，則在圖中連接 a 與 b
    }

    string sta, end;
    int t = 0;
    while (cin >> sta >> end) { // 處理多組查詢：每行包含起點 sta 與終點 end
        if (t++) cout << '\n'; // 在每組輸出之間印出空行
        map<string, int> vis; // 記錄是否已訪問
        map<string, string> path; // 保存每個節點的連接關係，用於回溯路徑
        queue<string> q;
        
        // 初始化 BFS：將起點加入佇列並標記已訪問
        q.push(sta), vis[sta] = true;

        while (!q.empty()) { // 執行 BFS，直到佇列為空或找到終點
            string now = q.front(); q.pop();
            if (now == end) break; // 找到終點即可停止搜尋
            for (auto i : mp[now]) if (!vis[i]) // 若相連且尚未拜訪過
                vis[i] = true, // 標記為已訪問
                q.push(i), // 將相連結點加入佇列
                path[i] = now; // 記錄從 i 返回 now 的父節點
        }

        string ans;
        if (path[end] == "") cout << "No solution.\n"; // 若 path 中沒有 end，代表無可達路徑
        else { // 反向回溯：從 end -> ... -> sta
            while (end != sta) ans += string(end.rbegin(), end.rend()) + "\n", end = path[end];
            cout << sta + string(ans.rbegin(), ans.rend()) << '\n';
        }
    }
}

練習題

Doublets解答