← 返回题目列表

AtCoder · abc364_b

D. 网格行走

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

有一个网格 H 行和 W 列。让 (i, j) 表示位于 i从顶部数第行和 j左起第 列。

细胞 (i, j) 为空,如果 C_{i, j} is .,并且如果不为空 C_{i, j} is #.

Takahashi 目前在牢房 (S_i, S_j),他将按照以下规则行事 i = 1, 2, \ldots, |X| 按顺序。

  • 如果 i- 第一个字符 X is L,并且当前单元格左侧的单元格存在且为空,则他移动到左侧的单元格。否则,他将留在当前牢房中。
  • 如果 i- 第一个字符 X is R,并且当前单元格右侧的单元格存在且为空,则他移动到右侧的单元格。否则,他将留在当前牢房中。
  • 如果 i- 第一个字符 X is U,并且当前单元格上方的单元格存在且为空,则他移动到上方的单元格。否则,他将留在当前牢房中。
  • 如果 i- 第一个字符 X is D,并且当前单元格下方的单元格存在且为空,则他移动到下方的单元格。否则,他将留在当前牢房中。

完成这一系列操作后打印他所在的单元格。

约束

  • 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} is . or #.
  • C_{S_i, S_j} = .
  • X 是长度介于 1 和 50,包含在内,由以下组成 L, R, U, D.

输入

输入由标准输入按以下格式给出:

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 is U,以及上面的单元格 (2, 1) 存在并且是一个空单元格,因此他移动到上面的单元格,即 (1, 1).
  • 第二个字符 X is L,以及左侧的单元格 (1, 1) 不存在,所以他停留在 (1, 1).
  • 第 3 个字符 X is D,以及下面的单元格 (1, 1) 存在并且是一个空单元格,因此他移动到下面的单元格,即 (2, 1).
  • 第 4 个字符 X is R,以及右侧的单元格 (2, 1) 存在并且是一个空单元格,因此他移动到右侧的单元格,即 (2, 2).
  • 第 5 个字符 X is U,以及上面的单元格 (2, 2) 存在,但不是空单元格,因此他停留在 (2, 2).

因此,在完成这一系列动作后,他就在牢房里了。 (2, 2).


示例输入 2

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

示例输出 2

2 4

示例输入 3

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

示例输出 3

1 1