题解 | #坐标移动#

坐标移动

http://www.nowcoder.com/practice/119bcca3befb405fbe58abe9c532eb29

题目的主要信息：

开发一个坐标计算工具， A表示向左移动，D表示向右移动，W表示向上移动，S表示向下移动
从（0,0）点开始移动，从输入字符串里面读取一些坐标，并输出最终结果
输入的合法坐标为A(或者D或者W或者S) + 数字（两位以内），坐标之间以;间隔
非法坐标不操作

方法一：模拟

具体做法：

我们可以遍历输入的字符串，以分号为界限，利用substr函数分割成较小的坐标，放入数组中。然后我们设置坐标为 $(0, 0)$ ，遍历字符串数组，对于每一个坐标首先检查其是否是空串或者长度是否在1到2之间，否则都是非法坐标，可以忽略。然后我们检查开头字母是否是ASDW中的一个，否则还是非法坐标。最后我们检查出去首字符的其他字符是否全是数字，如果出现了其他字符还是非法坐标，需要忽略。

对于合法坐标，我们遍历字符串后两位（有的只有1位），将字符转化成数字，然后利用switch选择ASDW相应的字母，对不同的坐标加减上面计算的数字。全部遍历完数组以后就可以输出了。

alt

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main(){
    string s;
    while(cin >> s){
        int x = 0;
        int y = 0;
        vector<string> everystr;
        for(int i = 0; i < s.length(); i++){
            int j = i;
            while(j < s.length() && s[j] != ';') //以分号为界限
                j++;
            everystr.push_back(s.substr(i, j - i)); //截取分号之间的部分加入数组
            i = j;
        }
        for(int i = 0; i < everystr.size(); i++){ //遍历字符串数组
            if(everystr[i].empty() || everystr[i].size() > 3 || everystr[i].size() < 2) //空串或者长度大于3或者小于2，忽略
                continue;
            //开头不为这四个字母也不合法，忽略
            if(everystr[i][0] != 'A' && everystr[i][0] != 'D' && everystr[i][0] != 'S' && everystr[i][0] != 'W')
                continue;
            bool flag = false;
            for(int j = 1; j < everystr[i].length(); j++) //查看方向后面除了数字还有无其他字符
                if(!(everystr[i][j] >= '0' && everystr[i][j] <= '9')){
                    flag = true;
                    break;
                }
            if(flag) //有其他字符，不合法
                continue;
            int dis = 0; //移动距离
            for(int j = 1; j < everystr[i].length(); j++)
                dis = 10 * dis + everystr[i][j] - '0'; //获取数字
            switch(everystr[i][0]){ //根据移动方向加减相应坐标
                case 'A': x -= dis; break;
                case 'D': x += dis; break;
                case 'W': y += dis; break;
                case 'S': y -= dis; break;
            }
        }
        cout << x << "," << y << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ， $n$ 为输入的字符串长度，不管是分割阶段还是计算阶段循环次数都不会超过最开始的字符串长度
空间复杂度： $O (n)$ ，最坏情况下，字符串数组vector最长为 $n$

方法二：正则表达式

具体做法：

上述方法一有两个改进的地方，首先我们可以利用getline函数在输入的时候就以分号为界限，每次输入刚好是一个坐标，就不用再分割，用数组保存了。

然后就是利用正则表达式匹配来识别是否是合法字符：合法字符就是ASDW中一个字母后面接上1位或者2位数字，正则表达式为"[ADWS]\d{1,2}$"。我们对于上面得到的每个坐标进行正则匹配，如果不合法就忽略，如果合法就像方法一一样计算距离然后利用switch对每种情况单独计算。

#include<iostream>
#include<string>
#include<regex>
using namespace std;

int main(){
    string s;
    string patten = "[ADWS]\\d{1,2}$";
    regex r(patten);
    int x = 0;
    int y = 0;
    while(getline(cin, s, ';')){ //读取的时候就以分号分割坐标
        if(!regex_match(s, r)) //非法坐标
            continue;
       int dis = 0; //移动距离
       for(int i = 1; i < s.length(); i++)
           dis = 10 * dis + s[i] - '0'; //获取数字
       switch(s[0]){ //根据移动方向加减相应坐标
           case 'A': x -= dis; break;
           case 'D': x += dis; break;
           case 'W': y += dis; break;
           case 'S': y -= dis; break;
       }
    }
    cout << x << "," << y << endl;
    return 0;
}

复杂度分析：