1039: 致命陷阱

SYH是一个富有探险精神的人。他小时候曾梦想周游世界、探寻稀世珍宝、从而走上人生巅峰……。然而，他现在却被现实所击倒，逐渐失去梦想，成为了一名程序员。

SYH昨天晚上做了一个梦。他梦见自己进入了一个大小为N*M的矩形藏宝室，在拿（tou）宝藏的时候，一不小心触发了报警机关。更加可怕的是，整个迷宫将会在K秒之后崩塌，坠入深渊。

迷宫由墙和踏板组成。由于SYH触发了机关，所有的踏板都变成了“悬空踏板”。一旦SYH踏上了悬空踏板，这个踏板将会在下一秒消失。也就是说：SYH不可以踏入之前走过的踏板或是待在一个踏板上超过一秒。

幸运的是SYH通过GPS定位到了迷宫的出口。不过迷宫出口的大门一直是关闭的，当且仅当第K秒来临的时候，迷宫的门才会打开1秒，SYH才能利用那一秒的间隙逃出迷宫。

已知SYH每秒钟可以往上、下、左、右，4个方向移动一个单位，移动的目标位置不可以是墙，现在SYH想要知道他是否有可能活着逃出去。

输入文件名为 trap.in。

第一行输入一个正整数T，表示测试数据的组数。

对于每组测试数据：

输入第一行有三个整数N、M、K，表示迷宫有N行M列，迷宫将会在K秒之后爆炸。

接下来是一个N*M的矩阵aij描述这张地图，其中aij是字符类型，地图仅包含下列元素：

1)       ‘.’表示悬空踏板

2)       ‘S’表示SYH的初始起点

3)       ‘D’表示迷宫大门的位置

4)       ‘X’表示墙

输出文件名为 trap.out。

输出共 T行，对于每组测试数据，如果SYH能够恰好在第K秒逃出迷宫，输出”YES”；否则，输出”NO”。

3
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
5 5 10
S..X.
...X.
..DX.
.....
.....

NO
YES
YES