A104184.马年冲线
入门
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
新年钟声将近,雾港城在广场上铺了一张巨大的方格地毯。小马从 (0,0) 出发,准备在倒计时归零前冲到烟花点 (xt,yt)。它一边跑一边嘀咕:
只要能到达那个地方……
它手里有一段移动记录,共 n 步,按顺序执行:
U:(x,y)→(x,y+1)D:(x,y)→(x,y−1)L:(x,y)→(x−1,y)R:(x,y)→(x+1,y)
但这段记录里可能夹杂了“手滑”。你最多可以进行 k 次撤销:
每次撤销可以选择任意一个位置的移动,并将该步从序列中删除(其余步保持原相对顺序执行)。
请你输出:要使小马最终恰好停在 (xt,yt),最少需要撤销多少步;如果在最多撤销 k 步的限制下做不到,输出 -1。
输入格式
第一行四个整数 n,k,xt,yt。
第二行一个长度为 n 的字符串 s,只包含 U、D、L、R。
输出格式
输出一个整数:最少撤销步数;若无法达成输出 -1。
输入输出样例
输入#1
5 3 2 1 RRUUL
输出#1
2
说明/提示
样例 1 说明
不撤销时终点为 (1,2)。撤销一次 L(相当于让 x 增加 1)与撤销一次 U(相当于让 y 减少 1),即可到达 (2,1),最少需要 2 次撤销。
数据范围
- 1≤n≤2×105
- 0≤k≤n
- ∣xt∣,∣yt∣≤2×105