← 返回题目列表

Codeforces · 1117/C

C. 魔法船

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

你是一艘船的船长。最初,你站在一个点 $$$(x_1, y_1)$$$(显然,海中的所有位置都可以用笛卡尔平面来描述),并且你想要前往一个点 $$$(x_2, y_2)$$$。

你知道天气预报——长度为$$$n$$$的字符串$$$s$$$,仅由字母U、D、L和R组成。该字母对应于风向。此外,预测是周期性的,例如第一天的风吹到一边$$$s_1$$$,第二天——$$$s_2$$$,第$$$n$$$天——$$$s_n$$$和第$$$(n+1)$$$天——$$$s_1$$$,等等。

船舶坐标按以下方式更改:

- 如果风向 U 吹,则船从 $$$(x, y)$$$ 移动到 $$$(x, y + 1)$$$;
- 如果风向 D 吹,则船从 $$$(x, y)$$$ 移动到 $$$(x, y - 1)$$$;
- 如果风向 L 方向吹,则船从 $$$(x, y)$$$ 移动到 $$$(x - 1, y)$$$;
- 如果风向 R 吹,那么船会从 $$$(x, y)$$$ 移动到 $$$(x + 1, y)$$$。

该船还可以前往四个方向之一或每天停留在原地。如果它通过了,那么它正好是 1 个距离单位。船和风的换位加起来。如果船停留在原地,那么只有风向才重要。例如,如果风向U吹,船向L方向移动,那么从点$$$(x, y)$$$它将移动到点$$$(x - 1, y + 1)$$$,如果它向U方向移动,那么它将移动到点$$$(x, y + 2)$$$。

您的任务是确定船舶到达点 $$$(x_2, y_2)$$$ 所需的最少天数。

输入

第一行包含两个整数 $$$x_1, y_1$$$ ($$$0 \le x_1, y_1 \le 10^9$$$) — 船舶的初始坐标。

第二行包含两个整数 $$$x_2, y_2$$$ ($$$0 \le x_2, y_2 \le 10^9$$$) — 目标点的坐标。

保证起始点坐标和目的点坐标不同。

第三行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串 $$$s$$$ 的长度。

第四行包含字符串 $$$s$$$ 本身,仅由字母 U、D、L 和 R 组成。

输出

唯一的一行应包含船舶到达点 $$$(x_2, y_2)$$$ 所需的最少天数。

如果不可能,则打印“-1”。

示例

输入 #1

0 0
4 6
3
UUU

输出 #1

5

输入 #2

0 3
0 0
3
UDD

输出 #2

3

输入 #3

0 0
0 1
1
L

输出 #3

-1

注意

在第一个示例中,船舶应执行以下移动序列:“RRRRU”。那么它的坐标就会相应地改变: $$$(0, 0)$$$ $$$\rightarrow$$$ $$$(1, 1)$$$ $$$\rightarrow$$$ $$$(2, 2)$$$ $$$\rightarrow$$$ $$$(3, 3)$$$ $$$\rightarrow$$$ $$$(4, 4)$$$ $$$\rightarrow$$$ $$$(4, 6)$$$。

在第二个示例中,船舶应执行以下移动序列:“DD”(应停留在原地的第三天)。那么它的坐标就会相应地改变: $$$(0, 3)$$$ $$$\rightarrow$$$ $$$(0, 3)$$$ $$$\rightarrow$$$ $$$(0, 1)$$$ $$$\rightarrow$$$ $$$(0, 0)$$$。

在第三个示例中,船永远无法到达 $$$(0, 1)$$$ 点。