牛客IOI周赛20-普及组 B-移动撤销

思路：栈 + 模拟

将所有操作对应的字符压栈，每次遇到撤销操作 时，判断栈是否为空，若不为空则弹出栈顶元素，相当于撤销一次操作，若为空则不做操作。由于四种操作都单独在 轴或单独在 轴上移动，所以与操作顺序无关，依次从栈里弹出操作并依次执行即可。

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    string a;
    cin >> a;
    stack<char> s;
    int x = 0, y = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] != 'Z') s.push(a[i]);
        else if(!s.empty()) s.pop();
    }

    while(!s.empty()) {
        char c = s.top();
        s.pop();
        if(c == 'W') y++;
        else if(c == 'A') x--;
        else if(c == 'S') y--;
        else if(c == 'D') x++;
    }
    cout << x << " " << y << endl;
}

复杂度分析

时间复杂度：
空间复杂度：，利用了辅助栈