Problem I: 迷宫搜索

Problem I: 迷宫搜索

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 281  Solved: 105
[Submit][Status][Web Board]

Description

迷宫的游戏,相信大家都听过,现在我们用一个n*m的矩阵表示一个迷宫,例如:
S.X.
..X.
..XD
....
其中‘S’表示起点,‘D’表示终点,‘X’表示该位置为墙,不可以走,‘.’表示可以通行。每次只能向“上下左右”四个方向移动一步。
你的任务是判断在x步内(小于等于x),能否从起点走到终点。

Input

第一行输入三个数n m x,分别表示迷宫的尺寸和步数。(1 < n,m < 7; 0 < x < 50)
接下来输入一个n*m的矩阵,描述迷宫的状态。

Output

判断是否能在x步内从起点走到终点,如果可以,输出“YES”,否则输出“NO”。

Sample Input

3 4 5
S.X.
..X.
...D

Sample Output

YES

HINT

[Submit][Status]