2011年10月8日 星期六

11545 - Avoiding Jungle in the Dark

Pilgrim打算長途跋涉前往聖地朝聖,路上可能會經過危險的區域,事實上,他會經過兩種路段:平地與叢林。在平地上不論一天的任何時刻都是安全的,但必須避免在晚上經過或停留在叢林中。另外,他不能不眠不休地連續旅行超過16個小時,最多16小時之後就必須休息,他可以在任何他想休息的時候休息,甚至連續一直休息也無所謂,不過一但他決定要休息,就必需整整休息8個小時。

給定路徑的地圖,請你幫他計算到達目的地所需的最短時間。

Input

輸入資料的第一列有一個正整數T(<= 100)表示測試資料的組數,每組資料一列,長度介於2~1000之間,且一定是以S開始以D結束,分別表示旅程的開始與結束,介於其中僅包含字元 '.'(表示平地)或 '*'(表示叢林),從一地到另一地剛好花上一個小時,且他只會前進不會後退。他一開始會在一地的最左邊,整整經過一個小時之後他會前進到下一塊地的最左邊。

Output


請每組測試資料輸出資料編號與到達目的地所須的最短時間,若無法到達目的地請輸出-1。旅途的第一天他位於S的位置且出發時刻為早上六點,晚上的時段定義為下午六點到早上六點。

Sample Input                              Output for Sample Input

3
S.......D
S...****................***.D
S***********.***********D
Case #1: 8
Case #2: 36
Case #3: -1

原文出處

沒有留言:

張貼留言