← 返回题目列表

AtCoder · mujin_pc_2018_e

E. 迷路

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

配点 : 500 点

問題文

N 行 M 有一个列网格。从上面 i 行,从左数 j 选择列中的方块。 由 (i,j) 代表。 特别是左上角的方块 (1,1) ,右下方块是 (N,M) 。

网格的状态是一个二维数组 s 什么时候可以工作s_{ij} 是 在 # 当广场 (i,j) 有障碍物;. 或 至少 S 或 至少 G 时没有障碍物。

机器人是 0 以秒为单位S 开始, 尝试在最短的时间内到达 G 广场。

然而,机器人不能总是向任何方向移动。

长度 小于或等于 K 的字符串所需的时间.在这次比赛中,参赛者按照以下条件进行打字. d 。每一秒,机器人都可以移动到相邻的方格或停留在当前所在的方格中。然而,t 秒后 t+1 几秒钟后, 除以t 该值应乘以 K 后的余数 r (0 \leq r \leq K-1)作为, 仅在 d_{r+1} 方向 1 需要几秒钟 只需移至 1 你可以继续前进。当前广场 (i,j) 当 如果d_{r+1} 是 在 U 输出 (i-1,j) 属于 D 输出 (i+1,j) 属于L 输出 (i,j-1) 属于 R 输出 (i,j+1) 。您无法移动到网格之外或移动到有障碍物的网格。

在这种情况下 找出到达 S 减去G 方块的最短时间。 包括

制約

  • 2 \leq N,M \leq 1000
  • 1 \leq K \leq 100000
  • s 是 您也可以写 # 或 至少 . 或 至少 S 或 至少 G 组成
  • S 和 按字典顺序比较 G 每个正方形有 1 存在
  • d 的长度是 K
  • d 是 您也可以写 U 或 至少 D 或 至少 L 或 至少 R 组成
  • N,M,K 是一个整数

入力

输入是按以下格式从标准输入给出的。

N M K
d_{1}...d_{K}
s_{11}...s_{1M}
:
s_{N1}...s_{NM}

出力

机器人 S 减去 G 所需的最短时间。然而,无论你如何移动 如果您无法移动到 S 减去 G 如果您无法搬到 -1 。


入力例 1

2 3 5
UDRRL
S..
.#G

出力例 1

7

入力例 2

3 3 5
UDUDD
S..
...
.G.

出力例 2

-1

无论你如何移动 2 无法移至列。


入力例 3

3 3 5
UDLRD
S..
.#.
..G

出力例 3

12