P16753 [GKS 2020 #B] Robot Path Decoding

你们国家的航天局刚刚在一颗新行星上着陆了一辆火星车。行星表面可以看作是一个包含 $10^9$ 列（从西到东编号为 $1$ 开始）和 $10^9$ 行（从北到南编号为 $1$ 开始）的方格网格。记 $(w, h)$ 表示第 $w$ 列、第 $h$ 行的方格。火星车从方格 $(1, 1)$ 出发。 火星车可以通过发送程序来操控，程序包含一个字符串，字符串中的字符代表四个基本方向的移动。机器人按顺序执行字符串中的每个字符。火星车的移动规则如下： - `N`：向北移动一个单位。 - `S`：向南移动一个单位。 - `E`：向东移动一个单位。 - `W`：向西移动一个单位。 此外，还有一种特殊指令 $\text{X}(\text{Y})$，其中 $\text{X}$ 是 $2$ 到 $9$（包含两端）之间的数字，$\text{Y}$ 是一个非空子程序。该指令表示机器人应重复执行子程序 $\text{Y}$ 共 $\text{X}$ 次。例如： - `2(NWE)` 等价于 `NWENWE`。 - `3(S2(E))` 等价于 `SEESEESEE`。 - `EEEE4(N)2(SS)` 等价于 `EEEEENNNNSSSS`。 由于行星是一个球体，第一列和最后一列相邻，因此从第 $10^9$ 列向东移动会使火星车移动到第 $1$ 列，从第 $10^9$ 行向南移动会使火星车移动到第 $1$ 行。类似地，从第 $1$ 列向西移动会使火星车移动到第 $10^9$ 列，从第 $1$ 行向北移动会使火星车移动到第 $10^9$ 行。给定一个机器人将要执行的程序，请确定机器人完成所有移动后的最终位置。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行，每行包含一个字符串：发送给火星车的程序。

对于每个测试用例，输出一行，格式为 `Case #x: w h`，其中 $x$ 是测试用例编号（从 $1$ 开始），$w$ 和 $h$ 是机器人最终所在的方格 $(w, h)$。

在样例 #1 中，火星车向南移动三格，然后向东移动三格。 在样例 #2 中，火星车向北移动一格。由于行星是一个环面，这会将其移动到第 $10^9$ 行。 在样例 #3 中，发给火星车的程序等价于 `NSSSNEEN`。 在样例 #4 中，发给火星车的程序等价于 `NWNWNWWEEEEWWEEEEWNWNWNWWEEEEWWEEEEW`。 ### 限制条件 $1 \le T \le 100$。 字符串表示一个有效的程序。 每个程序的长度在 $1$ 到 $2000$ 个字符之间（包含两端）。 **测试集 1** 单个测试用例中机器人执行的总移动步数不超过 $10^4$。 **测试集 2** 无额外限制。 翻译由 DeepSeek V4 Pro 完成