一只小狗在迷宫中发现了一根骨头，然而当他咬起骨头的时候，迷宫开始摇晃，小狗可以感觉到地面开始下沉。它意识到骨头可能是一个陷阱，它拼命的想要逃离这个迷宫。
迷宫是一个N*M的矩形，迷宫中只有一扇门。开始时，门是关闭的，只有在第T秒的时候开启一小段时间(小于1秒)。因此，小狗必须在第T秒时到达门口。在每一秒中，它可以从一个方块移动到上、下、左、右方向相邻的另一个方块，一旦进入一个方块，这个方块的地面将开始下沉并在下一秒消失，所以他不能在一个方块上停留超过一秒以上，也不能进入一个已经到过的方块。
这只小狗能够成功的逃离这个迷宫吗？

输入包含多组测试数据。对于每组测试数据：
第一行，是三个整数N,M,T(1＜M,N＜7；0＜T＜50),分别表示迷宫的尺寸以及门开启的时间。
接下来N行。每行包含M个字符，描述一个迷宫的地图。
地图中的字符含义如下：
'X':表示这个方块是墙，小狗不能进入此方块
'S':表示小狗开始的地点的方块
'D':表示门所在的方块
'.':表示空着的方块
当输入为"0 0 0"时表示所有的输入数据输入完毕

对于每组测试数据输出一行，如果小狗能够成功逃离迷宫输出'YES'否则输出'NO'

回溯 搜索 level5