Problem F
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 103 Accepted Submission(s) : 44
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
张晨乐在一个古老的迷宫中发现了一个手机，这个手机深深地吸引了他。
然而，当他拾起手机，迷宫开始摇晃，张晨乐能感觉到地面下沉。他意识到：这个手机只是一个诱饵！于是，他不顾一切地试图冲出这个迷宫。
迷宫是一个大小为N*M的矩形，有一扇门，一开始，门是关闭的，并在第T秒打开一瞬间（小于1秒的时间）。因此，张晨乐必须刚好在第T秒钟到达门口。
每一秒，他都可以向上，下，左，右四个相邻的位置中的任意一个移动。一旦他进入一个新的地方，这个地方的地面就会开始下沉，并在下一秒消失。因此，他不能在一个地方停留超过一秒钟，也不能再进入曾经走过的地方。
请问，可怜的张晨乐能够逃出迷宫吗？
然而，当他拾起手机，迷宫开始摇晃，张晨乐能感觉到地面下沉。他意识到：这个手机只是一个诱饵！于是，他不顾一切地试图冲出这个迷宫。
迷宫是一个大小为N*M的矩形，有一扇门，一开始，门是关闭的，并在第T秒打开一瞬间（小于1秒的时间）。因此，张晨乐必须刚好在第T秒钟到达门口。
每一秒，他都可以向上，下，左，右四个相邻的位置中的任意一个移动。一旦他进入一个新的地方，这个地方的地面就会开始下沉，并在下一秒消失。因此，他不能在一个地方停留超过一秒钟，也不能再进入曾经走过的地方。
请问，可怜的张晨乐能够逃出迷宫吗？
Input
输入由多个测试用例组成。
每个测试用例的第一行包含三个整数N，M和T（1 <N，M <7; 0 <T <50），分别表示迷宫的大小和门打开的时间。
接下来的N行给出迷宫布局，每行包含M个字符。
每个字符含义如下：
'X'：不能进入的墙
'S'：起点
'D'：门
'.'：可以行走的地方
输入以三个0结束，这个测试用例不被处理。
每个测试用例的第一行包含三个整数N，M和T（1 <N，M <7; 0 <T <50），分别表示迷宫的大小和门打开的时间。
接下来的N行给出迷宫布局，每行包含M个字符。
每个字符含义如下：
'X'：不能进入的墙
'S'：起点
'D'：门
'.'：可以行走的地方
输入以三个0结束，这个测试用例不被处理。
Output
对于每组测试数据，如果张晨乐能够逃出迷宫，则请输出“YES”，否则，请输出“NO”。每组数据输出占一行。
Sample Input
4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0
Sample Output
NO YES