Problem M: 致命陷阱

Problem M: 致命陷阱

Time Limit: 2 Sec  Memory Limit: 32 MB
Submit: 456  Solved: 104
[Submit] [Status] [Web Board] [Creator:]

Description

zser沉迷于某探险。现在zser在一次探险中的发现了一座古老的遗迹中发现了宝藏,当zser打开宝藏时,整个迷宫开始塌陷,zser想要逃离该迷宫。
遗迹为一个N*M的矩形,因为塌陷遗迹的有些路被封住了,并且该遗迹的大门在第t秒才会打开(在第t秒之前和之后遗迹的大门都是关闭的)。zser在每一秒中只能移动到上,下,左,右相邻的其中一个位置,并且zser一旦进入一个位置,该位置在一秒后便会塌陷。

Input

对于每组测试数据:
    第一行包含三个整数,分别为N,M,T(1 <= N, M < 7; 0 < T < 50),分别表示遗迹的大小和遗迹完全坍塌所需要的时间,接下来N行给出遗迹的布局,每行包含M个字符:
'X'代表墙,不能通过
'S'代表起点(保证存在起点)
'D'代表出口
'.'无障碍物
输入三个0代表输入结束

Output

如果zser能逃出遗迹便输出‘YES’,否则输出‘NO’ (不包含引号)

Sample Input Copy

4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
1 4 4
S..D
0 0 0

Sample Output Copy

NO
YES
NO

HINT

经典搜索剪枝题目