Codeforces Testing Round #16 C.Skier

题意: 一个人在雪地上滑雪,每次可以向上下左右四个方向移动一个单位,如果这条路径没有被访问过,则需要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;

}

巴特西

Codeforces Testing Round #16 C.Skier

最新文章

热门文章