問題文
无限宽二维网格的起源 (0, 0) 与高桥君 有 1 无人机。当给定一个字符串时,该无人机将计算字符串从头到尾的每个字符。 1 解释为两条指令并按顺序执行。命令如下 4 类型。
L当前无人机位置 (x, y) 作为 转到 (x-1, y) 移至R当前无人机位置 (x, y) 作为 转到 (x+1, y) 移至U当前无人机位置 (x, y) 作为 转到 (x, y+1) 移至D当前无人机位置 (x, y) 作为 转到 (x, y-1) 移至
现在无人机已收到一些移动到某处的命令。 Takahashi-kun 是一串字符,代表发送给无人机的命令。
我收到了 S ,但某些部件已损坏。?我不再明白了。然而,?原本是
我们知道这是角色L、R、U、D之一。
无人机和高桥先生之间的距离由无人机的位置决定。 曼哈顿距离为 (x,y) 由 |x|+|y| 代表。表示您要查找的值类型的整数 给出 T ,因此无人机完成移动后与高桥之间可能的距离, T=1 然后是最大值, T=2 如果是,请找到最小值。
入力
输入是按以下格式从标准输入给出的。
S T
- 1 表示第 1 行中向无人机发出的命令的字符串 给出了 S(1≦|S|≦10^5) 。在这里, 仅包含 |S| 是一个字符串 表示 S 的长度。
- S 是
L、R、U、D、?的 5 类型的字符。 - 2 一个整数,表示在行中查找的值的类型 T (1≦T≦2) 。
出力
- T=1 那么,无人机完成移动后与高桥先生之间可能的距离中,最大值为 在 1 行输出。
- T=2 然后,在无人机完成移动后与高桥先生之间的距离的可能值中,找到最小值。 1 行输出。
- 不要忘记换行符。
部分点
针对此问题设置了部分分数。 如果
- T=1 数据集的所有答案都正确 给出 100 点。
- 如果答案对于没有附加约束的数据集是正确的,则附加 1 给出积分,总分 获得 101 点。
入力例 1
UL? 1
出力例 1
3
- 无人机最终可能到达的地方是 (-2,1), (-1,0), (-1,2), (0,1) 的 4 一。无人机与高桥之间的距离 |x|+|y| 的最大值为 3 。
- 这种情况满足部分点相加约束。
入力例 2
UD? 1
出力例 2
1
- 无人机最终可能到达的地方是 (1,0), (-1,0), (0,1), (0,-1) 的 4 一。无人机与高桥之间的距离 |x|+|y| 的最大值为 1 。
- 这种情况满足部分点相加约束。
入力例 3
UUUU?DDR?LLLL 1
出力例 3
7
- 这种情况满足部分点相加约束。
入力例 4
UULL? 2
出力例 4
3
- 这种情况不满足部分点相加约束。