← 返回题目列表

Codeforces · 294/D

D. 沙斯和画家机器人

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

Shaass 认为全白色地砖的厨房太无聊了。他的厨房地板由 n·m 方砖组成,形成 n × m 矩形。因此,他决定将一些瓷砖涂成黑色,使地板看起来像棋盘,即任何相邻的瓷砖都不应该具有相同的颜色。

Shaass 想要使用画家机器人给瓷砖上色。一开始,机器人站在面向对角线方向(即左上、右上、左下或右下)的边界块(xs,ys)中。当机器人在厨房里行走时,他会对经过的每一块瓷砖进行涂漆,即使它之前已经涂过漆。绘制每块瓷砖需要消耗一单位的黑色油漆。如果机器人在任何时候撞到厨​​房的墙壁,他就会根据反射规则改变方向。请注意,当机器人从另一个图块进入该图块时,该图块会被绘制,换句话说,改变同一图块中的方向不会导致任何绘制。机器人站立的第一块瓷砖也已涂漆。

地板出现格子状时,机器人立即停止喷漆。给定厨房的尺寸和机器人的位置,找出机器人在停止涂地板之前消耗的油漆量。

让我们考虑下面描述的示例。

如果机器人从左网格的 1 号图块(图块 (1, 1))开始,向右下移动,它将经过 1354236 块图块,并在途中消耗 7 单位的黑色油漆,直到停在 6 号图块处。但是,如果它从右网格的 1 号图块开始,向右下移动,它将陷入循环绘制图块 1、2 和 3。

输入

输入的第一行包含两个整数 n 和 m,(2 ≤ n,m ≤ 105)。第二行包含两个整数 xs 和 ys (1 ≤ xs ≤ n, 1 ≤ ys ≤ m) 以及机器人最初面向的方向。 Direction 是字符串之一:“UL”(左上方向)、“UR”(右上方向)、“DL”(左下方向)或“DR”(右下方向)。

请注意,该记录 (xs, ys) 表示位于厨房左侧第 ys 列、顶部第 xs 行的瓷砖。

保证起始位置是边界图块(边邻图块少于四个的图块)。

输出

打印机器人获得格子厨房地板所消耗的油漆量。如果它从未发生过,则打印 -1。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。

示例

输入 #1

3 4
1 1 DR

输出 #1

7

输入 #2

3 4
3 3 DR

输出 #2

11

输入 #3

3 3
1 1 DR

输出 #3

-1

输入#4

3 3
1 2 DL

输出#4

4