---
description: UVa 429 解題心得
---
UVa 429 解題心得
===
# 題目
[**題目點我**]

## 懶人大意
:::info
每筆測資一開始先給許多字串建構**字典**
接下來輸入兩個字串為 **起始字** 及 **目標字**
**輸出**從起始字到目標字需要的**操作次數**
:::
## 此時
:::warning
阿 沒啥想法
看看hint "**BFS**"(廣度優先搜尋)
-->跟圖有關係
:::
## 圖
狀態看成點，狀態A可透過**一次操作**轉移至狀態B看成**狀態A到狀態B存在一條有向邊**
那從狀態S到狀態T最少要幾次操作，再透過BFS求得S到T的最短路徑
## 注意事項
:::danger
IO 極度麻煩
:::
## 那怎麼寫呢??
直接看註解ㄅ
# code

#include<bits/stdc++.h>
using namespace std;
#define maxn 205
int n;//n筆測資
vector<string> dic;//字典大全
map<string,int> vertex;//用map去搞定每個字串的編號 編號就是之後圖上的頂點
vector<int> adj[maxn];//用adjacency來存圖上的連通情況
int dis[maxn];//距離
bool vis[maxn];//BFS用
int bfs(int u,int v){
    //初始化
    memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    dis[u]=0;vis[u]=1;
    //開始BFS
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        int now=q.front();q.pop();
        if(now==v)break;
        for(auto i:adj[now]){
            if(vis[i])continue;
            q.push(i);
            dis[i]=dis[now]+1;//步數加1
            vis[i]=1;
        }
    }
    return dis[v];
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int count=0;count<n;count++){
        //初始化
        dic.clear();
        vertex.clear();
        for(int i=0;i<=maxn;i++)adj[i].clear();
        
        string s;
        int index=0;
        while(cin>>s){
            if(s=="*")break;
            dic.push_back(s);
            vertex[s]=index;
            for(int i=0;i<index;i++){//往回配對,看看有沒有和當前字串s需操作次數<=1的
                int different=0;
                for(int j=0;j<s.size();j++){
                    if(s[j]!=dic[i][j])different++;
                }
                if(different<=1){
                    adj[index].push_back(i);
                    adj[i].push_back(index);
                }
            }
            index++;
        }
        //終於建好圖了
        string qu;//question
        cin.ignore();
        while(getline(cin,qu)){//先依次讀整行
            if(qu=="")break;//遇到空白行跳出
            string str1,str2;
            //切成兩個字串
            int i=0;
            for(i=0;i<qu.size();i++){
                if(qu[i]==' ')break;
                else str1+=qu[i];
            }
            i++;
            for(;i<qu.size();i++){
                if(qu[i]==' ')break;
                else str2+=qu[i];
            }
            /*
                程式碼64~73行的更簡便的方法
                用.find找空白
                再用strtok切出來
            */
            cout<<str1<<' '<<str2<<' '<<bfs(vertex[str1],vertex[str2])<<endl;
        }
        if(count!=n-1)cout<<endl;
    }
    return 0;
}

>[name=陳奕帆]
###### tags: `UVa`