题目描述

贵国航天局的一辆探测车刚刚在一颗新行星上着陆了。

行星可以被看作一个 $10^9$ 列（自西向东，从 1 开始编号）$10^9$ 行（自北向南，从 1 开始编号）的方格矩阵。

设 $ (w,h) $ 表示第 $ w $ 列第 $ h $ 行的方格区域。

探测车最开始位于方格 (1,1) 内。

可以通过向探测车发送指令来操控其在行星表面移动。

指令是一个字符串，由表示四个基本方向运动的字符构成。

探测车将按顺序执行字符串中的每个字符：

• $N$：向北移动一个单位。

• $S$：向南移动一个单位。

• $E$：向东移动一个单位。

• $W$：向西移动一个单位。

还有一个特殊指令 $X(Y)$，其中 $X$ 是 2 到 9 之间的一个数字，$Y$ 是一个非空的子指令。

这表示探测车需要将子指令 $Y$ 重复执行 $X$ 次，例如：

• 2(NWE) 等同于 NWENWE。

• 3(S2(E)) 等同于 SEESEESEE。

• EEEE4(N)2(SS) 等同于 EEEENNNNSSSS。

由于这颗行星是一个环面，所以第一列与最后一列是相邻的，第一行与最后一行也是相邻的。

也就是说，从第 $10^9$ 列向东移动将移动至第 1 列，从第 1 列向西移动将移动至第 $10^9$ 列，从第 $10^9$ 行向南移动将移动至第 1 行，从第 1 行向北移动将移动至第 $10^9$ 行。

给定探测车将要执行的完整指令，请确定探测车完成所有移动后的最终位置。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据占一行，包含一个字符串，表示探测车要执行的移动指令。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为Case #x: w h，其中 $x$ 为组别编号（从 1 开始），$(w,h)$ 表示探测车的最终位置。

数据范围

$1≤T≤100$,
每个字符串的长度范围 $[1,2000]$。

输入样例

4
SSSEEE
N
N3(S)N2(E)N
2(3(NW)2(W2(EE)W))

输入样例

Case #1: 4 4
Case #2: 1 1000000000
Case #3: 3 1
Case #4: 3 999999995

样例解释

在示例 1 中，探测车向南移动三个单位距离，然后向东移动三个单位距离。

在示例 2 中，探测车向北移动一个单位距离，由于行星是环面，所以它移动至第 $10^9$ 行。

在示例 3 中，探测车的移动指令等效于 NSSSNEEN。

在示例 4 中，探测车的移动指令等效于 NWNWNWWEEEEWWEEEEWNWNWNWWEEEEWWEEEEW。

算法1

(模拟 + 栈思想) $O(n)$

把字符串当作栈来操作，分为下面几类进行操作：
这里用了两个栈
moves栈用来存储操作
xs，ys栈用来存储位置

• 当遇见字母或倍数，直接入栈moves

• 当遇见左括号，将(0, 0)入栈xs和ys作为一个基坐标值

• 当遇见右括号，先取出xs，ys的栈顶坐标值，先执行括号内部的操作，然后出栈括号和取出倍数，然后依次取出xs和ys剩余的基坐标值，然后加上倍数后的值。

时间复杂度

栈操作，时间复杂度接近$O(n)$

参考文献

KickStart

C++ 代码

#include<iostream>
#include<stack>
using namespace std;
typedef long long LL;

int T;
LL ans;
LL MOD = 1E9;
string ops;

LL mod(LL a, LL b) {
    LL res = a % b;
    return res >= 0 ? res : res + b;
}

LL run(const char c, LL &x, LL &y) {
    if(c == 'N') y = mod(y - 1, MOD);
    if(c == 'S') y = mod(y + 1, MOD);
    if(c == 'E') x = mod(x + 1, MOD);
    if(c == 'W') x = mod(x - 1, MOD);
}

pair<int, int> solve() {
    stack<char> moves;
    stack<LL> xs, ys;
    LL x = 0, y = 0;

    for(int i = 0; i < ops.size(); i ++) {
        if(ops[i] == ')') {
            LL xx = xs.top(), yy = ys.top();
            xs.pop();
            ys.pop();

            while(moves.top()!= '(') {
                char c = moves.top();
                run(c, xx, yy);
                moves.pop();
            }

            moves.pop();//左括号出栈
            int time = moves.top() - '0'; //倍数出栈
            moves.pop();

            if(xs.size()) {
                xs.top() = mod(xs.top() + xx * time, MOD);
                ys.top() = mod(ys.top() + yy * time, MOD);
            }else {
                x = mod(x + xx * time, MOD);
                y = mod(y + yy * time, MOD);
            }
        }else {
            if(ops[i] == '(') {
                xs.push(0);
                ys.push(0);
            }
            moves.push(ops[i]);
        }
    }
    while(moves.size()) {
        char c = moves.top();
        run(c, x, y);
        moves.pop();
    }
    return make_pair(x + 1, y + 1);
}

int main()
{
    cin >> T;
    for(int i = 1; i <= T; i ++) {
        cin >> ops;
        pair<int, int> ans = solve();
        cout << "Case #" << i << ": " << ans.first << " " << ans.second << endl;
    }
    return 0;
}