Problem J: Johnny Qiang & Cydornia Knight
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$19$ |
正确数量 |
$13$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
搜索 图论 |
当前分类(单击移除)：
搜索图论
单击选择分类：
Johnny Qiang和Cydornia Knight是一对好朋友。不过很不幸，这对好朋友同时爱上了一个美丽的姑娘GJ。Johnny Qiang和Cydornia Knight不想因此而伤害了他们之间的感情，但他们也都不想轻易放弃对GJ的爱。于是他们决定，如果Cydornia Knight能够在K步之内（包括K步）采完Johnny Qiang家后花园里的玫瑰花（当然是为GJ所种的），Johnny Qiang就就退出，成全Cydornia Knight和GJ，若不能，Cydornia Knight就主动退出。
Johnny Qiang家的后花园是一个M*N的矩阵，里面有的地方种了玫瑰花，有的地方种了树，有的地方是草地。只有草地和长有玫瑰花的地方才能通行。Cydornia Knight从花园的左上角开始，每次可以走向与他（上下左右）邻接的任意一点，但是对于那些种了树的点，Cydornia Knight不可以走。每当Cydornia Knight走到种有玫瑰花的点，他就采下这个点所种的玫瑰花（采花不花费任何时间）。
现在请你写个程序判断谁必须要放弃对GJ的爱（注：Cydornia Knight很聪明，他一定会走最优的路线）。
包含多组数据。输入数据的第一行包含了三个整数M，N（1<=M,N<=20)，K。接下来的M行每行都有一个长度为N的字符串，其中‘g’代表草地，‘t’代表树，‘r’代表玫瑰
花（‘r’的出现次数不会超过16）。当M、N、K都等于0的时候，输入结束。
输出仅包含一行。如果Johnny Qiang必须退出，则输出“Poor Johnny,he will never get GJ.”。如果Cydornia Knight必须退出，则输出“Poor Cydornia,he will never get GJ.”。
4 4 8
gggg
trtg
gtrg
gggg
4 4 6
gggg
trtg
gtrg
gggg
0 0 0
Poor Johnny,he will never get GJ.
Poor Cydornia,he will never get GJ.
状态搜索