回分類題庫
h076: E.山中小屋的背叛者
關鍵字: NPSC 2010 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 512000 KB
Accepted : 10 Times / 10 Users | Submit : 130 Times / 16 Users | Accepted rate : 62%
題目加入時間 : 2012-11-04 02:21

Content: 简体中文

一天晚上,你和朋友們一起到山上一間破舊的空屋冒險。你們走過一間又一間的房間,尋找一些有趣的事物。在探索房子的同時,你們也發現一些神秘又令人戰慄的徵兆,它彷彿在預言你們的命運。

在你不知不覺的時候,一個朋友秘密地背叛了你們,投向邪惡勢力!他正在安排黑暗魔法,打算把你們的靈魂統統奉獻給黑魔王!你們必須在他的魔法完成以前擊敗他,以逃離魂飛魄散的命運。

根據你們之前發現的徵兆,只要你們依序輸入神聖的關鍵密語,你們就可以獲得聖光的保護,而背叛者會受到強烈的攻擊而灰飛煙滅。輸入關鍵密語的方式是這樣的:

由這間房子的平面圖可知,房子的外觀是方正的矩形,共有 R 排房間,每一排恰有 C 間,每一間房間都有門和它前後左右四間連通。每個房間裡面都有一個按鈕,上面有一個字母,按下這個按鈕就代表輸入了這個字母。你可以在所有房間裡自由移動,經過一間房間的時候可以按房間裡的按鈕至多一次。(下次經過才可以按下一次)按下按鈕代表輸入這個按鈕對應的字母,不按的話代表輸入空白。

神聖的關鍵密語共有 N 個單字,每個單字最多有 L 個字母。你需要依序輸入關鍵密語的每個單字。一個單字必須連續輸入,中間不能有空白;不過兩個單字之間和第一個單字以前都可以有零至多個空白。

現在你在第一排的第一個房間,你有房子的平面圖以及每個房間按鈕的對應字母表,還知道完整的關鍵密語。請問最少需要經過幾個房間才能輸入完神聖的關鍵密語,徹底擊潰背叛者呢?

Input:

第一行有一個整數 T,代表接下來有幾組測試資料。

每一筆的第一行有三個整數,R C N。接下來有 R 行,每行有 C 個字母,第 i 行的第 j 個字母 aij 代表第 i 排的第 j 個房間裡的按鈕的對應字母。再來有 N 行,每行有 1 至 L 個字母,依序表示神聖的關鍵密語的每個單字。

Output:

請對每筆測試資料輸出一個整數,代表最少需要經過的房間數。若無法完整輸入神聖的關鍵密語,請輸出 Betrayal!。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
2 2 2
ab
dc
ab
d
2 3 1
abc
def
zzzzz

Sample Output :

4
Betrayal!

Hint :

Author :

NPSC 2010 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum