# 題目: UVa 429 - Word Transformation

# 題目說明

有一種字謎叫word transformation
給你一個字，每次改變一個字母使之成為一個新單字，最終變得與目標字一樣
你的目標是找到一開始的字需要經過多少次轉換會變成目標字

---

INPUT:
輸入第一行有一個整數N，代表總共有幾個set
接著空一行
接下來會連續輸入字串，直到*符號
*之後，每行會有兩個字串，前者為一開始的字，後者為目標字
當輸入為空行時，結束這個set

---

OUTPUT:
先輸出每個開始字及目標字，接著輸出轉換的數量
每個set會隔一行

# 解題方法

先用map建表，將差一個字元的字連在一起，將著再bfs找出轉換的數量
因為用到cin及getline，所以要呼叫cin.ignore()清空緩衝區

# 參考程式碼

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <sstream>
#include <queue>

using namespace std;

map<string, vector<string>> G;

int bfs(string s1, string s2)
{
    queue<string> Q;
    map<string, bool> vis;
    map<string, int> dis;

    Q.emplace(s1);
    vis[s1] = true;
    dis[s1] += 0;

    while (!Q.empty())
    {
        string u = Q.front();
        Q.pop();
        if (u == s2) break;

        for (auto& v : G[u]) if (!vis[v])
        {
            Q.emplace(v);
            dis[v] = dis[u] + 1;
            vis[v] = true;
        }
    }

    return dis[s2];
}

int main()
{
    // fast io
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    vector<string> V;
    string str, s1, s2;
    int N;

    cin >> N;
    cin.ignore();
    getline(cin, str); // blank line

    while (N--)
    {
        V.clear();
        G.clear();

        // store data and build graph
        while (getline(cin, str), str != "*")
        {
            for (auto i : V)
            {
                int dif = 0;

                for (int j = 0; j < min(i.size(), str.size()); ++j) 
                    if (str[j] != i[j]) ++dif;          

                if (dif <= 1)
                {
                    G[i].emplace_back(str);
                    G[str].emplace_back(i);
                }
            }

            V.emplace_back(str);
        }

        // search for key and target
        while (getline(cin, str), str != "")
        {
            stringstream ss(str);
            ss >> s1 >> s2;

            cout << s1 << " " << s2 << " " << bfs(s1, s2) << "\n";
        }

        if (N) cout << "\n";
    }

    return 0;
}

# 參考文章:

https://tnlolicon.blogspot.com/2018/12/uva-429-word-transformation.html
https://hackmd.io/@D2F0DLkmQcGOdq_jvg3BGw/Hy_59VWKm?type=view