12797: Letters ★★★☆☆ 題組：Problem Set Archive with Online Judge 解題者：林必祥 解題日期：2017年5月23日 題意：給定一個N×N公園(2≦N≦100)，求從座標(1,1)走到座標(N,N)的最短路徑(只能往上下左右四個方向移動)，且需符合以下規則：每個座標都會是a~j或是A~J其中一個字母，最後選擇的路徑不可以同時包含某字母的大小寫。
題意範例： 6 DdaAaA. D. CBAcca. C. eEaeeE. e. ee. bBbabB. b. bab. DbDdDc 題意範例： 6 DdaAaA D..... CBAcca C..... eEaeeE e..ee. bBbabB b.bab. DbDdDc DbD.D. fFaAaC ....aC 輸出13 7 aAaaaaa aAaaaaa aAaaaAa aAaaaAa aAaaaAA aAaaaAA aaAaAaa aaAaAaa AaAaaAa AaAaaAa aaAAaAa aaAAaAa aaaaaAa aaaaaAa 輸出-1(找不到)
解法： 分析題目，給定的N×N矩陣中，要找出(1,1)到(N,N)的最短路徑。透過一般的搜索方式( BFS / DFS )去找最短路徑。 然而，如何知道最短路徑發生的情況是哪些字母選大寫，哪些選小寫呢？ 回到題目敘述，字母只有可能是abcdefghijABCDEFGHIJ，十個字母的大小寫。 因此，直接枚舉所有的組合，然後跑圖的搜索。 a b c … h i j A B C H I J 1 ...
解法： 這樣的方法，時間不會超過嗎？ 時間複雜度：O(210. N 解法： 這樣的方法，時間不會超過嗎？ 時間複雜度：O(210*N*N)，最大約為107。 枚舉所有的字母情況組合，該怎麼做？ 提供一個遞迴的方法。 bool arr[256]; // initial as false void rec(int i) { // start at rec(0) if (i == 10) { bfs(); return; } arr[‘a’+i] = true; arr[‘A’+i] = false; rec(i+1); arr[‘a’+i] = false; arr[‘A’+i] = true; // exchange rec(i+1); }
解題範例：無 討論： 時間複雜度：O(210*N*N) N的範圍：2≦N≦100