Description

小狗在一个古老的迷宫里发现了一根骨头，这使他非常着迷。然而，当他捡起它时，迷宫开始摇晃，小狗能感觉到地面下沉。他意识到骨头是个陷阱，他拼命想走出这个迷宫。
迷宫是一个长方形，大小是N×M。迷宫里有一扇门。一开始，门是关着的，它会在第T秒打开很短一段时间（不到1秒）。因此，小狗必须在第T秒到达门口。每隔一秒钟，他可以移动到上下左右相邻的位置。一旦他到达这个位置，这个地面就会开始下沉，并在下一秒消失。他不能在一个街区停留超过一秒钟，也不能回到一个已经到过的位置。可怜的小狗能活下来吗？请帮帮他。

Input Format

输入包含三个整数N、M和T（1<N，M<7；0<T<50），分别表示迷宫的大小和门打开的时间。接下来的N行给出迷宫布局，每行包含M个字符。字符是下列字符之一：

“X”：一堵墙，小狗不能进去；
“S”：小狗的起点；
“D”：门；或
“.”：空块。

Output Format

如果小狗能够存活，则在一行中输出“YES”，否则输出“NO”。

5 5 6
...X.
..XD.
.....
SX...
..X..

NO

Source

深搜