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. 多組查詢：輸出結果之間以空行分隔。

## 程式碼

```cpp
#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';
    }
  }
}