回分類題庫
h090: E.神雕大俠的困境
關鍵字: NPSC 2011 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 19 Times / 16 Users | Submit : 27 Times / 17 Users | Accepted rate : 94%
題目加入時間 : 2012-11-04 02:27

Content: 简体中文

在襄陽抵禦蒙古軍一戰,『神雕大俠』楊過苦戰金輪國師。雙方激戰了數千餘招,修練了數十年的真力激盪在戰場上。最後,楊過終於使出畢生絕技「黯然銷魂掌」。

在出掌的那一剎那,楊過頓感真氣微塞,心中暗叫不妙,尤其在這種驚險時刻,勝負生死多在一招之間。情急之下楊過奮力擊出全身的內力,終於打敗金輪國師。

待戰事結束,大俠郭靖隨即為楊過把脈。這脈不把還好,一把之下郭靖猛然驚覺:楊過因為長年在外與人拼鬥,身上早就為許多奇異內功所傷;又因楊過喜好行俠仗義,鮮少安靜下來靜心調養,多處瘀血阻塞了真氣。若不儘速治好,少則內功修為停滯不前,多則可能減壽數年。所幸郭靖征戰多年,熟知行醫之道,連忙找來襄陽城中最好的畫師為楊過臨摹出一幅「五臟六腑圖」。根據黃藥師長年的研究,只要依據這張「五臟六腑圖」從體外施以猛烈的掌擊即可清除經脈內的瘀血。

如下圖A即為「五臟六腑圖」,其中 A 和 B 代表兩個不同的臟腑,而*則代表瘀血所在之處。郭靖可從上方或左方的任一處以垂直或水平方向施以「降龍十八掌」,則可清除掌力觸及的瘀血(如圖B),同時,若掌力觸及臟腑則會令之受傷。

為了避免造成過大的副作用,郭靖決定在不傷及太多臟腑的前提下清除所有經脈中的瘀血,他是否能成功呢?

Input:

輸入的第一行有一個正整數 T,代表測試資料的組數(1<=T<=100)。

每組測試資料以三個整數 N, M, K 開頭,其中 N 代表「五臟六腑圖」的大小,M 代表臟腑的數量,K 代表最多可以傷及幾個臟腑。(1<=N<=20, 0<=M<=10, K<=M)

接下來 N 行為楊過的「五臟六腑圖」,其中臟腑只會由大寫英文字母表示,順序是由 'A' 到 'Z'。

Output:

對於每筆輸入資料,如果郭靖能在最多傷及 K 個臟腑的狀況下清除所有瘀血則輸出 yes,否則輸出 no。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
5 2 1
....*
*AA..
*A**.
..*.B
..*BB
3 1 0
AAA
A*A
AAA

Sample Output :

yes
no

Hint :

Author :

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

  Solve it!   Status Forum