時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
虛擬鍵盤是一個矩形網格，每個按鍵佔據一個或多個互相連通的單位格。同一個字元只對應一個按鍵，但該按鍵可能包含多格。 游標一開始位於左上角。硬體只有上、下、左、右及選取五個按鈕，每按一次都算一次按鍵操作。 按方向鍵時，游標沿該方向越過所有仍屬於目前按鍵的格子，停在該方向第一個屬於不同按鍵的格子；若該方向直到邊界都沒有不同按鍵，游標不移動。選取則將目前按鍵的字元加到輸入文字尾端。 輸入完指定文字後，還必須移到以 * 表示的 Enter 按鍵並選取它。請求完成全部輸入所需的最少操作次數。
輸入格式
多筆資料，讀至檔案結尾。每筆第一行為 r c，1 ≤ r, c ≤ 50。接著 r 行，每行 c 個字元，表示鍵盤。 鍵盤字元只可能是大寫英文字母、數字、- 與 *，同字元的所有格子保證形成連通區域。 最後一行是要輸入的非空文字，長度不超過 10000，只含鍵盤上可用且不是 * 的字元。保證文字可被輸入。
輸出格式
每筆輸出一行最少操作次數，包含所有方向鍵、每個字元的選取，以及最後選取 Enter 的操作。
題目來源：UVa 1714 — Keyboarding。 原題：https://onlinejudge.org/external/17/1714.pdf
範例測資
範例輸入 1
4 7 ABCDEFG HIJKLMN OPQRSTU VWXYZ** CONTEST 5 20 12233445566778899000 QQWWEERRTTYYUUIIOOPP -AASSDDFFGGHHJJKKLL* --ZZXXCCVVBBNNMM--** -------------------- ACM-ICPC-WORLD-FINALS-2015 2 19 ABCDEFGHIJKLMNOPQZY X*****************Y AZAZ 6 4 AXYB BBBB KLMB OPQB DEFB GHI* AB
範例輸出 1
30 160 19 7
請先登入後再提交程式碼
討論與題解
載入討論區…