#2326. 魔法船

魔法船

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在二维的平面上,小明驾驶着一架飞船,起点为(x1,y1)\red{(x1,y1),}终点为(x2,y2)\red{(x2,y2)}

小明知道了接下来的天气预报,每天都会吹上、下、左、右中一个方向的风。天气预报可以用一个字符 串s\red{s}表示,包含U,D,L,R\red{U,D,L,R}四种字母,表示吹上、下、左、右中一个方向的风。其中第一天的风向为s1\red{s_1} ,第二天吹的风向为s2,...\red{s_2,...}n\red{n}天吹的风向为sn\red{s_n,}n+1\red{n+1}天吹的风向为s1...\red{s_1...}以此类推。

假如吹的风往上, 船会从(x,y)\red{(x,y)}移动到(x,y+1)\red{(x,y+1)};

假如吹的风往下,船会从(x,y)\red{(x,y)}移动到(x,y1)\red{(x,y-1)};

假如吹的风往左, 船会从(x,y)\red{(x,y)}移动到(x1,y)\red{(x-1,y)};

假如吹的风往右, 船会从(x,y)\red{(x,y)}移动到(x+1,y)\red{(x+1,y)};

同时小明每天也可以从上下左右中选择一个方向,移动一个单位,即每天的位移为风向和小明自己移动 的叠加。例如某天风向向上,小明往左移动了一个单位,那么小明会从(x,y)\red{(x,y)}移动到(x1,y+1)\red{(x-1,y+1)}

你现在需要帮助小明,计算出最少需要多少天可以到达终点。

输入格式

第一行两个整数表示x1,y1\red{x1,y1}

第二行两个整数表示x2,y2\red{x2,y2}

第三行一个整数 ,表示s\red{s}的长度。

第四行,字符串s\red{s}

输出格式

输出最少可以到达目的地的天数,如果到达不了输出1\red{-1}

样例

输入样例

0 0
4 6
3
UUU

输出样例

5

提示

对于50%\red{50\%}的数据,1<=n<=1000,0<=x1,y1,x2,y2<=1000\red{1<=n<=1000,0<=x1,y1,x2,y2<=1000}

对于100%\red{100\%}的数据,1<=n<=105,0<=x1,y1,x2,y2<=109\red{1<=n<=10^5,0<=x1,y1,x2,y2<=10^9}

国庆集训11

未参加
状态
已结束
规则
IOI
题目
7
开始于
2022-10-6 9:00
结束于
2022-10-6 12:00
持续时间
3 小时
主持人
参赛人数
12