问题 T: hero in maze II

问题 T: hero in maze II

时间限制: 1 Sec  内存限制: 128 MB
提交: 87  解决: 42
[提交] [状态] [讨论版] [命题人:]

题目描述

500年前,Jesse是我国最卓越的剑客。他英俊潇洒,而且机智过人^_^。
突然有一天,Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了,他急忙赶到迷宫,开始到处寻找公主的下落。令人头痛的是,Jesse是个没什么方向感的人,因此,他在行走过程中,不能转太多弯了,否则他会晕倒的。 我们假定Jesse和公主所在的位置都是空地,初始时,Jesse所面向的方向未定,他可以选择4个方向的任何一个出发,而不算成一次转弯。希望你帮他判断一下他是否有机会找到心爱的公主。

输入

题目包括多组测试数据.

第1行为一个整数T(1 ≤ T≤ 100),表示测试数据的个数,接下来为T组测试数据.

每组测试数据以两个整数N,M,K(1<=N, M≤100, 0<K<=10)开头,分别代表迷宫的高,长和Jesse最多能转的弯数,(紧接着有N行,M列字符,由".","*","P","S"组成。其中 
"." 代表能够行走的空地。 
"*" 代表墙壁,Jesse不能从此通过。 
"P" 是公主所在的位置。 
"S" 是Jesse的起始位置。 
每个时间段里Jesse只能选择“上、下、左、右”任意一方向走一步



输出

如果Jesse能在晕之前找到公主,输出“YES”,否则输出“NO”。

样例输入

2
5 5 1
P..**
*.**.
S....
.....
*....
5 5 2
P..**
*.**.
S....
.....
*....

样例输出

NO
YES

[提交][状态]