← 返回题目列表

AtCoder · agc033_b

B. LRUD 游戏

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

分数: 600 点

问题陈述

我们有一个由正方形组成的矩形网格 H 水平行和 W 垂直列。让 (i,j) 表示 i从顶部开始的第行和 j左起第 列。 在这个网格上,有一个棋子,最初放置在正方形 (s_r,s_c).

高桥和青木将玩一个游戏,每个玩家都有一个长度的字符串 N。 高桥的弦是 S,青木的字符串是 T. S 和 T 均由四种字母组成: L, R, U 和 D.

游戏包括 N 步骤。的 i第一步进行如下:

  • 首先,高桥执行一个动作。他要么将棋子朝以下方向移动 S_i,或者不移动棋子。
  • 其次,青木执行了一个动作。他要么将棋子朝以下方向移动 T_i,或者不移动棋子。

这里,将棋子朝以下方向移动 L, R, U 和 D,是将棋子从方格中移出 (r,c) 到正方形 分别为 (r,c-1), (r,c+1), (r-1,c) 和 (r+1,c)。如果目标方格不存在,则该棋子将从网格中移除,游戏结束,即使小于 N 步骤已完成。

高桥想要从其中一个网格中删除该棋子 N 步骤。 另一方面,青木想要完成 N 继续前进,棋子仍留在网格上。 确定当双方都发挥最佳状态时,棋子是否会在游戏结束时保留在网格上。

约束

  • 2 \leq H,W \leq 2 \times 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq s_r \leq H
  • 1 \leq s_c \leq W
  • |S|=|T|=N
  • S 和 T 由四种字母组成 L, R, U 和 D.

输入

输入由标准输入按以下格式给出:

H W N
s_r s_c
S
T

输出

如果游戏结束时该棋子仍保留在网格上,则打印 YES;否则,打印 NO.


示例输入 1

2 3 3
2 2
RRL
LUD

示例输出 1

YES

这是游戏的一个可能的进展:

  • 高桥向右移动棋子。该作品现在位于 (2,3).
  • 青木将棋子向左移动。该作品现在位于 (2,2).
  • 高桥没有移动棋子。该作品仍保留在 (2,2).
  • 青木将棋子向上移动。该作品现在位于 (1,2).
  • 高桥将棋子向左移动。该作品现在位于 (1,1).
  • 青木没有移动棋子。该作品仍保留在 (1,1).

示例输入 2

4 3 5
2 2
UDRRR
LLDUD

示例输出 2

NO

示例输入 3

5 6 11
2 1
RLDRRUDDLRL
URRDRLLDLRD

示例输出 3

NO