D. 走迷宫(maze)

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

在一个神秘的迷宫世界里,有一个n行m列的网格。你从坐标(sx,sy)的位置出发,进行t次移动。每次移动可以选择

往上(U)、往下(D)、往左(L)、往右(R)四个方向之一移动一格。

若在某一次移动中,你要前往的位置是迷宫边界之外,则你将会从另一侧出现在迷宫中,即上边界的某一列的最下面,

或下边界的某一列的最上面,或左边界的某一行的最右边,或右边界的某一行的最左边。

迷宫中的“#”表示障碍物,如果下一个要走到的位置是障碍物,则此步移动为原地踏步。请你计算经过t次移动后,最终走到的格子位置。

输入格式

第一行包括三个正整数n,m,t,分别表示迷宫的行数、列数和移动的次数。

接下来n行,每行包含一个长度为m的字符串,表示迷宫的布局。其中‘#’表示障碍物,‘.’表示空位置。

接下来一行包含两个整数sx和sy,表示出发位置的坐标,其中 0<=sx<n, 0<=sy<m

接下来t行,每行一个字符(U、D、L、R四个字符中的一个),依次表示每次移动的方向。

输出格式

输出一行包含以空格隔开的两个整数,依次表示最终移动到的格子位置。

样例

样例输入1

3 4 5
....
.#..
....
1 2
D
D
L
D
R

样例输出1

0 2

样例解释

从(1,2)出发,进行5i移动:

1.向下移动,最终位置(2,2);

2.向下移动,到达边界之外,最终位置(0,2);

3.向左移动,最终位置(0,1);

4.向下移动,有障碍物,最终位置(0,1);

5.向右移动,最终位置(0,2);

最终走到的格子位置为(0,2)。

数据范围与提示

对于20%的测试数据,保证图中没有障碍物;

对于另外20%的测试数据,保证 1<=n,m<=10,t=1

对于另外40%的测试数据,保证 1<=n,m<=1000,保证只会朝一个方向移动

对于100%的测试数据,保证 1<=n,m<=1000,1<=t<=10^3, 0<=sx<n, 0<=sy<m ;