codeforces1351 C. Skier(结构体作键值 重载运算符)

C. Skier

Skier rides on a snowy field. Its movements can be described by a string of characters 'S', 'N', 'W', 'E' (which correspond to 11 meter movement in the south, north, west or east direction respectively).

It is known that if he moves along a previously unvisited segment of a path (i.e. this segment of the path is visited the first time), then the time of such movement is 55 seconds. If he rolls along previously visited segment of a path (i.e., this segment of the path has been covered by his path before), then it takes 11 second.

Find the skier's time to roll all the path.

Input

The first line contains an integer tt (1≤t≤1041≤t≤104) — the number of test cases in the input. Then tt test cases follow.

Each set is given by one nonempty string of the characters 'S', 'N', 'W', 'E'. The length of the string does not exceed 105105 characters.

The sum of the lengths of tt given lines over all test cases in the input does not exceed 105105.

Output

For each test case, print the desired path time in seconds.

Example

input

Copy

5
NNN
NS
WWEN
WWEE
NWNWS

output

Copy

15
6
16
12
25

结构体作为map、set等容器的键值时,需重载 < 号,重载时注意使用 if 、else if 、else 重载

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-12;
const double PI = acos(-1.0);
const int N = 2e5 + 5;

struct node
{
    int x1, y1, x2, y2;
    node(){};
    node(int xx1, int yy1, int xx2, int yy2):x1(xx1), y1(yy1), x2(xx2), y2(yy2){}
    bool operator < (const node &a)const
    {
        if(x1 != a.x1)
            return x1 > a.x1;
        else if(y1 != a.y1)
            return y1 > a.y1;
        else if(x2 != a.x2)
            return x2 > a.x2;
        else
            return y2 > a.y2;
    }
};

int main()
{
    int t;
    string s;
    scanf("%d", &t);
    while(t--)
    {
        cin >> s;
        int len = s.size();
        map<node, int>mp;
        int prex = 0;
        int prey = 0;
        int x = 0;
        int y = 0;
        int cnt = 0;
        for(int i = 0; i < len; ++i)
        {
            switch(s[i])
            {
            case 'N':
                y++;
                break;
            case 'S':
                y--;
                break;
            case 'E':
                x++;
                break;
            case 'W':
                x--;
                break;
            }
            if(mp.count(node(prex, prey, x, y)))
            {
                cnt++;
            }
            else
            {
                mp[node(prex, prey, x, y)]++;
                mp[node(x, y, prex, prey)]++;
            }
            prex = x;
            prey = y;
        }
        cout<<cnt + (len - cnt) * 5<<'\n';
    }
    return 0;
}

 

全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
06-12 10:50
门头沟学院 Java
你的不定积分没加C:我怎么在学院群看到了同样的话
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务