題目: UVa - 429 - Word Transformation
題目說明
給一些在字典裡面的字串,在這些字串中,若兩個字串只相差了一個字元,就可以進行轉換,給原本的字串跟目標字串,求轉換幾次後能得到目標字串。
Input: 第一行為一整數 T
,代表有 T
組測資,後面接一個空行,之後每行會有一個字串,代表字典裡面的字,直到讀到 "*"
為止,之後每行會有兩個字串,分別代表原本的字串跟目標字串,直到讀到空行為止。空行後就是下一組測資。
Output: 輸出原本的字串及目標字串,及轉換的次數 ( 題目應該是保證會有答案 )。
解題思路
可以透過建圖,將題目的問題轉換成最短路徑的問題,先讀取測資,並將字串兩兩判斷,若兩字串只相差一個字元就建邊 ( 注意這裡要建雙向,因為兩者可相互轉換 ),之後讀取原本的字串跟目標字串,從原本的字串開始 BFS 求解即可。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
| #include <iostream> #include <algorithm> #include <sstream> #include <unordered_set> #include <unordered_map> #include <string> #include <vector> #include <queue>
using namespace std;
#define SIZE(c) int(c.size())
static auto __ = [] { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();
string orgin; string target; unordered_map<string, vector<string>> G; unordered_set<string> visited;
int bfs() { queue<string> q; q.push(orgin); visited.insert(orgin);
int dis = 0; while (!q.empty()) { int size = q.size();
while (size--) { auto u = q.front(); q.pop(); if (u == target) return dis;
for (auto& v : G[u]) if (!visited.count(v)) q.push(v), visited.insert(v); } ++dis; } }
int main() { int T; string str;
cin >> T; cin.ignore(); getline(cin, str);
while (T--) { G.clear();
int cnt = 0; string tmp[200]; while (getline(cin, str) && str != "*") tmp[cnt++] = str;
for (int i = 0; i < cnt; ++i) for (int j = i + 1; j < cnt; ++j) { if (SIZE(tmp[i]) != SIZE(tmp[j])) continue;
int dif = 0; for (int k = 0; k < SIZE(tmp[i]); ++k) { if (tmp[i][k] != tmp[j][k]) ++dif; }
if (dif == 1) G[tmp[i]].push_back(tmp[j]), G[tmp[j]].push_back(tmp[i]); }
while (getline(cin, str) && !str.empty()) { visited.clear(); stringstream ss(str); ss >> orgin >> target;
cout << orgin << ' ' << target << ' '; cout << bfs() << '\n'; }
if (T) cout << '\n'; } }
|
參考資料
UVa 429 /Word Transformation