题目描述

在一个无限大的平面直角坐标系中，牛牛初始站在坐标原点（即坐标（0,0））。
现在牛牛可以进行5种操作：
'W'：牛牛离开当前格子，向上走一步。即从(x,y)到(x,y+1)。
'A'：牛牛离开当前格子，向左走一步。即从(x,y)到(x-1,y)。
'S'：牛牛离开当前格子，向下走一步。即从(x,y)到(x,y-1)。
'D'：牛牛离开当前格子，向右走一步。即从(x,y)到(x+1,y)。
'Z'：牛牛撤销上一步操作，回到之前的格子。
特殊的，若已没有操作可以撤销，则牛牛不进行任何操作。
现在输入牛牛进行的所有操作，请输出牛牛最终所在的坐标。

输入描述

第一行一个正整数n，代表操作的数量。
第二行一个长度为n的、仅由'W'、'A'、'S'、'D和'Z'这五种字符构成的字符串。

输出描述

两个整数x和y，用空格隔开。表示牛牛最终的坐标。

示例1

输入

5
AWZZD

输出

1 0

说明

牛牛的五次操作：(0,0)->(-1,0)->(-1,1)->(-1,0)->(0,0)->(1,0)

示例2

输入

2
ZS

输出

0 -1

说明

牛牛的两次操作：(0,0)->(0,0)->(0,-1)

备注

对于20%的样例，图片说明 ，且字符串中没有'Z'字符。
对于另外20%的样例，图片说明 ，且所有的Z均不为无效撤销操作。
对于100%的样例，图片说明 。

解法

思考

如果是上下左右移动都好说，只是如果是Z撤回就麻烦了一点。
可以在输入的时候不直接移动，而是把他们用数组c保存下来，用一个值loc记录下下一个移动应该在数组中的位置，如果是上下左右，就存入数组并loc++，否则如果是撤回操作，loc--，在下次输入的时候就把该撤回的操作覆盖掉了（不覆盖也没关系）。但是注意loc不能为负，最多减到0.

AC代码

#include<bits/stdc++.h>
using namespace std;
char c[100010];
int main()
{
    int x=0,y=0;//初始位置(0,0)
    int n,loc=0;//操作首先放到数组中的0下标的位置
    cin>>n;getchar();//过滤掉换行
    char op;
    for(int i=0;i<n;i++)
    {
        op=getchar();
        if(op=='Z'&&loc)loc--;//如果是撤回并且loc!=0
        else c[loc++]=op;//否则储存操作并且loc++
    }
    for(int i=0;i<loc;i++)
    {
        switch(c[i])
        {
                        //做出相应的移动
            case 'W':y++;break;
            case 'A':x--;break;
            case 'S':y--;break;
            case 'D':x++;break;
        }
    }
    printf("%d %d\n",x,y);//输出结果
    return 0;
}