2013年7月30日 星期二

168 - Theseus and the Minotaur

在希臘神話中,有一個傳說「忒修斯(Theseus)和牛頭怪」 這是一個不太可能的故事,故事中參雜了一個牛頭的怪物、充滿曲折的地下迷宮、失戀的女孩以及線球。在這次競賽的教育性質上,我們要揭露這個真實故事。

迷宮有很多洞窟,每個洞窟經由幾個通道可以通往其他洞窟,而其中幾個只能單向通行。為了設下陷阱抓到牛頭怪,忒修斯發現牛頭怪怕光,於是帶著大量的蠟燭進入迷宮。

忒修斯在迷宮四處找尋,最後他聽到牛頭怪從通道另一端傳來的聲音,從那個時刻開始,忒修斯點燃蠟燭並且展開追逐行動,牛頭怪會離開原本的洞窟,並且移動到下一個洞窟。而忒修斯慢慢地跟著牛頭怪移動,當每經過 k 個洞窟,他將會在此點燃一個蠟燭放下,當他快速點燃蠟燭後,會繼續跟蹤牛頭怪。由於有蠟燭的洞窟牛頭怪不會靠近,因此將會限制住牛頭怪的移動。

當牛頭怪離開洞窟時,會依序檢察其它不存在蠟燭的洞窟,找到第一個可去的地方並且移動,最後牛頭怪會被困住無法移動,忒修斯將可以戰勝牠。

迷宮類似於下圖表示,而牛頭怪離開的時候就好比按照字典順序檢查:







假設忒修斯在 C,他會聽到牛頭怪從 A 傳來的聲音,假設 k = 3,而走的順序依序為 A, B, D(忒修斯在此放下點燃的蠟燭), G, E, F(再放一個), H, E, G(再放一個), H, E(牛頭怪最後受困的地點)。

備註翻譯:由於忒修斯尾隨牠,牛頭怪不會走回上次的洞窟。



寫一個程式模擬整個追逐過程,所有洞窟將只會用大寫英文字母表示,並且按照順序打印出蠟燭的放置,以及最後牛頭怪被困的洞窟。

Input

輸入有多組測資,每組用一行表示圖形以及忒修斯位置、牛頭怪位置、k

每一行不超過 255 個字元。

讀到 '#' 結束程式。

Output

對於每組測資,按照順序輸出蠟燭的放置(追逐時的順序),以及牛頭怪最後的位置。

Sample input

A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
#

Sample output

D F G /E