76. 移动游戏

单点时限: 2.0 sec

内存限制: 256 MB

给定初始位置 $(0,0)$ 和目标位置 $(a,b)$,从一个位置可进行上下左右四个方向的移动。现给定一个移动命令序列,请判断是否能通过执行该序列,从初始位置达到目标位置。

移动命令格式如下:

  • U: $(x,y) \rightarrow (x,y+1)$
  • D: $(x,y) \rightarrow (x,y-1)$
  • L: $(x,y) \rightarrow (x-1,y)$
  • R: $(x,y) \rightarrow (x+1,y)$

移动命令序列必须从前往后一个一个命令执行。执行完之后从头开始继续一个一个执行。直到移动到目标位置就可停止。

一个命令都不执行也是符合要求的。

输入格式

第一行输入一个长度不超过 $100$ 个字符的移动命令序列 $s$,$s$ 只包含字符: U, D, L, R

第二行一个整数 $q$,表示询问数。

接下来 $q$ 行,每行输入两个整数 $a$ 和 $b$,表示目标位置 $(a, b)$。

部分分约定:

  • $30\%$: $-100 \le a,b \le 100$, 保证只会出现 U, D 或只会出现 L, R, $1 \le q \le 100$;
  • $70\%$: $|a|,|b| \le 200, 1 \le q \le 10^5$;
  • $100\%$: $|a|,|b| \le 10^9, 1 \le q \le 10^5$.

输出格式

对于每次询问,如果从 $(0,0)$ 能移动到目标位置则输出 Yes 否则输出 No

样例

Input
UUUD
4
0 -1
0 0
0 4
0 2
Output
No
Yes
Yes
Yes
Input
RU
2
2 2
1 2
Output
Yes
No
Input
DRLU
1
0 -1
Output
Yes

提示

序列为 UUUD 时,$(0,0)$ 可以通过什么也不执行得到。$(0,4)$ 可以通过执行 UUUDUU 得到。

326 人解决,580 人已尝试。

525 份提交通过,共有 4408 份提交。

3.7 EMB 奖励。

创建: 6 年,10 月前.

修改: 5 年,1 月前.

最后提交: 4 月,3 周前.

来源: 2018 实训第一次机考

题目标签