立体推箱子

题目描述

达达发明了一种立体推箱子游戏。

他发明的游戏里并没有那么多的规则和限制，在他的设定里游戏具有无限的平面空间，并且所有的区域都属于硬地。

终点永远都位于坐标 $(0,0)$ 处，请你求出从起点到终点所需的最少移动次数。

游戏规则

长方体在平面上移动，有三种状态：

1. 竖立状态 (U)：长方体覆盖一个格子 $(x,y)$
2. 水平状态 (H)：长方体与y轴平行，覆盖两个格子 $(x,y)$ 和 $(x,y+1)$
3. 垂直状态 (V)：长方体与x轴平行，覆盖两个格子 $(x,y)$ 和 $(x+1,y)$

输入格式

输入包含多组测试用例。

每组测试数据在一行内，格式为：C x y

其中：

• C 为一个字母，表示长方体的状态
  • U：长方体是竖立的
  • V：长方体与x轴平行，且其覆盖的另一个格子为 $(x+1,y)$
  • H：长方体与y轴平行，且其覆盖的另一个格子为 $(x,y+1)$
• x, y 是两个整数，表示长方体覆盖的格子坐标

输出格式

对于每个测试用例，输出一个占一行的整数，表示所需的最少移动次数。

数据范围

$0 \le x, y \le 1000000000$ （即坐标最大可达 $10^9$）

输入样例

U 0 0
H 0 0
V 1 0

输出样例

0
4
1

样例解释

第一个测试用例：U 0 0

• 长方体状态：竖立 (U)
• 位置：$(0,0)$
• 终点位置：$(0,0)$
• 由于长方体已经在终点位置且状态正确，所以不需要移动
• 输出：0

第二个测试用例：H 0 0

• 长方体状态：水平 (H)，覆盖 $(0,0)$ 和 $(0,1)$
• 终点位置：$(0,0)$
• 需要移动长方体到终点位置并调整为竖立状态
• 最少需要 4 步移动
• 输出：4

第三个测试用例：V 1 0

• 长方体状态：垂直 (V)，覆盖 $(1,0)$ 和 $(2,0)$
• 终点位置：$(0,0)$
• 需要移动长方体到终点位置并调整为竖立状态
• 最少需要 1 步移动
• 输出：1

移动规则

长方体可以在平面上移动，每次移动会改变其位置和可能的状态。具体的移动规则参考立体推箱子游戏的标准规则（题目参考172题）。

关键点：

1. 平面无限大，没有边界限制
2. 所有地面都是硬地，长方体可以在任何位置
3. 终点固定为 $(0,0)$，且要求长方体最终竖立在 $(0,0)$
4. 需要计算从初始状态到终点状态的最少移动次数

坐标范围说明

坐标范围很大（最大 $10^9$），因此不能使用基于网格的BFS等算法，需要数学方法或状态压缩技巧。

时空限制

• 时间限制：1秒
• 空间限制：64MB