问题1195--车辆调度

1195: 车辆调度

[命题人 : ]
时间限制 : 5.000 sec  内存限制 : 256 MB

题目描述

张老师设计了一个智能调度系统来控制他的遥控车队,今天,他带着他的车队来到黄渡理工大学的一块空地上测试这个系统。

这块空地可以描述为一个 w * h 大小的长方形,广场上有一些障碍物,几个目标点,当然,还有张老师的车队。

每分钟,调度系统会智能地向其中的一辆遥控车发送以下指令的其中一条:

1. 向北走,直到撞到空地的边界、障碍物或其他遥控车;

2. 向南走,直到撞到空地的边界、障碍物或其他遥控车;

3. 向西走,直到撞到空地的边界、障碍物或其他遥控车;

4. 向东走,直到撞到空地的边界、障碍物或其他遥控车;
    

 每条指令都会在一分钟之内完成,也就是说,空地上最多只有一辆遥控车在运动。此外,当遥控车无法向相应的方向移动时,它会停在原地。 



你想知道,在第 k 分钟时,有没有可能有任意一辆遥控车处在任意一个目标点上。

输入

第一行输入三个数字 w, h, k (1  w, h 10, 1 k 5) , 含义在题目描述中已给出。

接下来 h 行,每行输入一个长度为 w 的字符串 si,其中第i行的第j个字符表示(i, j)位置的状态。

其中,'R' 代表该位置初始有一辆遥控车,'X' 代表该位置有障碍物,'D' 代表该位置是一个目标点,'.' 代表该位置可以正常通过。

数据保证广场上的遥控车不超过4辆。

输出

如果k分钟后有可能有任意一个遥控车处在任意一个目标点上,输出 "YES", 否则输出 "NO"

样例输入 Copy

6 5 4
.....R
...X..
..D...
....D.
R.R...

样例输出 Copy

YES

提示

样例1中,遥控车可以按下述路线移动:
.....R
...X..
..D...
....D.
R.R...
R.....
...X..
..D...
....D.
R.R...
R.....
R..X..
..D...
....D.
..R...
R.....
..RX..
..D...
....D.
..R...
R.....
..RX..
..R...
....D.
......
4分钟时,有一辆遥控车达到了目标点。于是输出"YES"

来源/分类