← 返回题目列表

Codeforces · 606/B

B. 测试机器人

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

控制论失败 (CF) 组织制作了炸弹技术员机器人的原型。为了找出可能存在的问题,决定进行一系列测试。在每次测试开始时,机器人原型将被放置在大小为 x × y 的矩形方格区域的单元格 (x0, y0) 中,之后将在该区域的其中一个方格中安装地雷。每次将地雷安装到以前从未使用过的正方形时,它应该进行精确的 x·y 测试。机器人的起始单元始终保持不变。

将物体放置在场地上后,机器人必须运行字符串 s 给出的一系列命令,该字符串仅包含字符“L”、“R”、“U”、“D”。这些命令告诉机器人向左、向右、向上或向下移动一格,或者如果不可能沿给定方向移动则保持空闲。一旦机器人完成所有命令序列,它就会由于代码中的错误而爆炸。但是,如果在某个时刻机器人与地雷处于同一格子中,它也会爆炸,但不是由于代码中的错误。

向左移动会减少坐标 y,向右移动会增加坐标 y。同样,向上移动会减少 x 坐标,向下移动会增加 x 坐标。

测试可能会持续很长时间,因此您的任务是预测其结果。对于从 0 到 length(s) 的每个 k,您的任务是找出机器人在爆炸之前将执行多少次测试。

输入

输入的第一行包含四个整数 x, y, x0, y0 (1 ≤ x, y ≤ 500, 1 ≤ x0 ≤ x, 1 ≤ y0 ≤ y) - 场地的大小和机器人的起始坐标。坐标轴 X 向下,Y 轴向右。

第二行包含一系列命令,应由机器人执行。它的长度为 1 到 100 000 个字符,并且仅由字符“L”、“R”、“U”、“D”组成。

输出

打印由 (length(s) + 1) 个数字组成的序列。在第 k 个位置上,从零开始,打印机器人在爆炸之前将运行 k 个命令的测试次数。

示例

输入 #1

3 4 2 2
UURDRDRL

输出 #1

1 1 0 1 1 1 1 0 6

输入 #2

2 2 2 2
ULD

输出 #2

1 1 1 1

注意

在第一个示例中,如果我们排除地雷的可能影响,机器人的路线将如下所示:$$(2,2)\rightarrow(1,2)\rightarrow(1,3)\rightarrow(2,4)\rightarrow(3,3)$$。