题意: 一个人在雪地上滑雪,每次可以向上下左右四个方向移动一个单位,如果这条路径没有被访问过,则需要5秒的时间,如果被访问过,则需要1秒(注意:判断的是两点之间的距离,不是单纯的点).给你他的行动轨迹,求消耗的时间.

题解:我们用两个pair来维护边,用map来对边进行标记,每次更新map记得双向更新即可(e.g:(1,2)和(2,1)两个方向都要标记).

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
using namespace std;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<PII,PII> PP;

int t;
string s;
int cnt;
PII o,p;
PP S1,S2;
map<PP,bool> mp;


int main() {
    ios::sync_with_stdio(false);
    cin>>t;
     while(t--){
         p=o={0,0};
         cnt=0;
         cin>>s;
         mp.clear();
          for(char c:s){
              if(c=='N') p.se++;
              else if(c=='S') p.se--;
              else if(c=='W') p.fi--;
              else if(c=='E') p.fi++;
              S1={o,p};
              S2={p,o};
              if(mp[S1]) cnt++;
              else{
                  cnt+=5;
                  mp[S1]=mp[S2]=true;
              }
              o=p;
          }
          printf("%d\n",cnt);
     }
    return 0;
}