← 返回题目列表

AtCoder · abc035_b

B. 无人机

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

問題文

无限宽二维网格的起源 (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
  • 这种情况不满足部分点相加约束。