Download presentation
Presentation is loading. Please wait.
1
1757: Secret Chamber at Mount Rushmore
★★★☆☆ 題組：Problem Set Archive with Online Judge 題號：1757: Secret Chamber at Mount Rushmore 解題者：吳政軒 解題日期：2019年4月25日 題意：給定兩個正整數m(1~500),n(1~50)，接下來m行各有兩個英文字母s,t，表示s可以轉換成t，最後有n行，每行兩個字串p,q，問p是否可藉由上述轉換規則轉換成q 字母保證只有小寫的a-z
2
題意範例： (2)a無法變h (3)字數不相等 (4)i可先轉成r再轉換成o
3
解法：可以把題目給的轉換規則視作一個有向圖(如上頁)，並建立一個關於字母轉換的二維陣列，利用矩陣乘法確定那些字母可以轉換(eg
解法範例：無 討論： (1)題目並沒有規定給的字串長度必須相等(事實上範例測資就有長度不等的) (2)矩陣初始化不只有題目給的那些是1，還有自己到自己也是(下一頁的line34) (3)複雜度方面：矩陣乘法是O(k^3), k=26，因為只有26個字母；而字串比較是O(s)，其中s是字串長度較小的那個的長度
4
部分程式碼：
Similar presentations
