B - Grid Walk Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

H 行 W 列のグリッドがあります。グリッドの上から i 番目、左から j 番目のマスをマス (i, j) と表記します。

マス (i, j) は C_{i, j} が . のとき空きマスであり、# のとき空きマスではありません。

高橋君は現在マス (S_i, S_j) におり、i = 1, 2, \ldots, |X| の順に以下のルールに従って行動します。

  • X の i 文字目が L のとき、高橋君が現在いるマスの 1 つ左のマスが存在し、そのマスが空きマスならば 1 つ左のマスに移動する。そうでないならば、現在いるマスに留まる。
  • X の i 文字目が R のとき、高橋君が現在いるマスの 1 つ右のマスが存在し、そのマスが空きマスならば 1 つ右のマスに移動する。そうでないならば、現在いるマスに留まる。
  • X の i 文字目が U のとき、高橋君が現在いるマスの 1 つ上のマスが存在し、そのマスが空きマスならば 1 つ上のマスに移動する。そうでないならば、現在いるマスに留まる。
  • X の i 文字目が D のとき、高橋君が現在いるマスの 1 つ下のマスが存在し、そのマスが空きマスならば 1 つ下のマスに移動する。そうでないならば、現在いるマスに留まる。

一連の行動を終えた後高橋君がどのマスにいるか出力してください。

制約

  • 1 \leq H, W \leq 50
  • 1 \leq S_i \leq H
  • 1 \leq S_j \leq W
  • H, W, S_i, S_j は整数
  • C_{i, j} は . または #
  • C_{S_i, S_j} = .
  • X は L, R, U, D からなる長さ 1 以上 50 以下の文字列

入力

入力は以下の形式で標準入力から与えられる。

H W
S_i S_j
C_{1, 1}C_{1, 2}\ldotsC_{1, W}
C_{2, 1}C_{2, 2}\ldotsC_{2, W}
\vdots
C_{H, 1}C_{H, 2}\ldotsC_{H, W}
X

出力

高橋君が一連の行動を終えた後にいるマスをマス (x, y) として、x と y をこの順に空白区切りで出力せよ。

入力例 1

2 3
2 1
.#.
...
ULDRU

出力例 1

2 2

高橋君ははじめマス (2, 1) にいます。高橋君の一連の行動は以下のようになります。

  • X の 1 文字目は U であり、マス (2, 1) の 1 つ上のマスは存在し、そのマスは空きマスであるため 1 つ上のマスであるマス (1, 1) に移動する。
  • X の 2 文字目は L であり、マス (1, 1) の 1 つ左のマスは存在しないためマス (1, 1) に留まる。
  • X の 3 文字目は D であり、マス (1, 1) の 1 つ下のマスは存在し、そのマスは空きマスであるため 1 つ下のマスであるマス (2, 1) に移動する。
  • X の 4 文字目は R であり、マス (2, 1) の 1 つ右のマスは存在し、そのマスは空きマスであるため 1 つ右のマスであるマス (2, 2) に移動する。
  • X の 5 文字目は U であり、マス (2, 2) の 1 つ上のマスは存在するが、そのマスは空きマスではないためマス (2, 2) に留まる。

したがって一連の行動を終えた後に高橋君がいるマスはマス (2, 2) です。

入力例 2

4 4
4 2
....
.#..
...#
....
DUUUURULRD

出力例 2

2 4

入力例 3

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

出力例 3

1 1

Score : 200 points

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Cell (i, j) is empty if C_{i, j} is ., and not empty if C_{i, j} is #.

Takahashi is currently at cell (S_i, S_j), and he will act according to the following rules for i = 1, 2, \ldots, |X| in order.

  • If the i-th character of X is L, and the cell to the left of his current cell exists and is empty, he moves to the cell to the left. Otherwise, he stays in the current cell.
  • If the i-th character of X is R, and the cell to the right of his current cell exists and is empty, he moves to the cell to the right. Otherwise, he stays in the current cell.
  • If the i-th character of X is U, and the cell above his current cell exists and is empty, he moves to the cell above. Otherwise, he stays in the current cell.
  • If the i-th character of X is D, and the cell below his current cell exists and is empty, he moves to the cell below. Otherwise, he stays in the current cell.

Print the cell where he is after completing the series of actions.

Constraints

  • 1 \leq H, W \leq 50
  • 1 \leq S_i \leq H
  • 1 \leq S_j \leq W
  • H, W, S_i, S_j are integers.
  • C_{i, j} is . or #.
  • C_{S_i, S_j} = .
  • X is a string of length between 1 and 50, inclusive, consisting of L, R, U, D.

Input

The input is given from Standard Input in the following format:

H W
S_i S_j
C_{1, 1}C_{1, 2}\ldotsC_{1, W}
C_{2, 1}C_{2, 2}\ldotsC_{2, W}
\vdots
C_{H, 1}C_{H, 2}\ldotsC_{H, W}
X

Output

Let (x, y) be the cell where Takahashi is after completing the series of actions. Print x and y, separated by a space.

Sample Input 1

2 3
2 1
.#.
...
ULDRU

Sample Output 1

2 2

Takahashi starts at cell (2, 1). His series of actions are as follows:

  • The 1st character of X is U, and the cell above (2, 1) exists and is an empty cell, so he moves to the cell above, which is (1, 1).
  • The 2nd character of X is L, and the cell to the left of (1, 1) does not exist, so he stays at (1, 1).
  • The 3rd character of X is D, and the cell below (1, 1) exists and is an empty cell, so he moves to the cell below, which is (2, 1).
  • The 4th character of X is R, and the cell to the right of (2, 1) exists and is an empty cell, so he moves to the cell to the right, which is (2, 2).
  • The 5th character of X is U, and the cell above (2, 2) exists but is not an empty cell, so he stays at (2, 2).

Therefore, after completing the series of actions, he is at cell (2, 2).

Sample Input 2

4 4
4 2
....
.#..
...#
....
DUUUURULRD

Sample Output 2

2 4

Sample Input 3

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

Sample Output 3

1 1