Content:
简体中文
一天晚上,你和朋友們一起到山上一間破舊的空屋冒險。你們走過一間又一間的房間,尋找一些有趣的事物。在探索房子的同時,你們也發現一些神秘又令人戰慄的徵兆,它彷彿在預言你們的命運。
在你不知不覺的時候,一個朋友秘密地背叛了你們,投向邪惡勢力!他正在安排黑暗魔法,打算把你們的靈魂統統奉獻給黑魔王!你們必須在他的魔法完成以前擊敗他,以逃離魂飛魄散的命運。
根據你們之前發現的徵兆,只要你們依序輸入神聖的關鍵密語,你們就可以獲得聖光的保護,而背叛者會受到強烈的攻擊而灰飛煙滅。輸入關鍵密語的方式是這樣的:
由這間房子的平面圖可知,房子的外觀是方正的矩形,共有 R 排房間,每一排恰有 C 間,每一間房間都有門和它前後左右四間連通。每個房間裡面都有一個按鈕,上面有一個字母,按下這個按鈕就代表輸入了這個字母。你可以在所有房間裡自由移動,經過一間房間的時候可以按房間裡的按鈕至多一次。(下次經過才可以按下一次)按下按鈕代表輸入這個按鈕對應的字母,不按的話代表輸入空白。
神聖的關鍵密語共有 N 個單字,每個單字最多有 L 個字母。你需要依序輸入關鍵密語的每個單字。一個單字必須連續輸入,中間不能有空白;不過兩個單字之間和第一個單字以前都可以有零至多個空白。
現在你在第一排的第一個房間,你有房子的平面圖以及每個房間按鈕的對應字母表,還知道完整的關鍵密語。請問最少需要經過幾個房間才能輸入完神聖的關鍵密語,徹底擊潰背叛者呢?
Input:
第一行有一個整數 T,代表接下來有幾組測試資料。
每一筆的第一行有三個整數,R C N。接下來有 R 行,每行有 C 個字母,第 i 行的第 j 個字母 aij 代表第 i 排的第 j 個房間裡的按鈕的對應字母。再來有 N 行,每行有 1 至 L 個字母,依序表示神聖的關鍵密語的每個單字。
Output:
Sample Input:
2 2 2 2 ab dc ab d 2 3 1 abc def zzzzz
Sample Output :
4 Betrayal!
Hint
:
Author
: