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;
}

 

全部评论

相关推荐

点赞 评论 收藏
分享
frutiger:逆天,我家就安阳的,这hr咋能说3k的,你送外卖不比这工资高得多?还说大厂来的6k,打发叫花子的呢?这hr是怎么做到说昧良心的话的
找工作时遇到的神仙HR
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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