Skier (Codeforces 1351C)
Tags: Implement, data structures

Skier rides on a snowy field. Its movements can be described by a string of characters 'S', 'N', 'W', 'E' (which correspond to $$$1$$$ 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 $$$5$$$ 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 $$$1$$$ second.Find the skier's time to roll all the path.

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the input. Then $$$t$$$ 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 $$$10^5$$$ characters.The sum of the lengths of $$$t$$$ given lines over all test cases in the input does not exceed $$$10^5$$$.

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


Sample Inputs:
5
NNN
NS
WWEN
WWEE
NWNWS

Sample Outputs:
15
6
16
12
25

Solution (Python):
for _ in range(int(input())):
    s = input()
    ans = 0
    (x, y) = (0, 0)
    d = {}
    for i in s:
        x1 = x
        y1 = y
        if i == 'N':
            y += 1
        elif i == 'S':
            y -= 1
        elif i == 'E':
            x += 1
        else:
            x -= 1
        if d.get((x1, y1, x, y), 0) != 0 or d.get((x, y, x1, y1), 0) != 0:
            ans += 1
        else:
            d[x1, y1, x, y] = 1
            ans += 5
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

def II():
    return int(sys.stdin.readline())

def MI():
    return map(int, sys.stdin.readline().split())

def LI():
    return list(map(int, sys.stdin.readline().split()))

def SI():
    return sys.stdin.readline()[:-1]

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def LLI1(rows_number):
    return [LI1() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1

def MI1():
    return map(int1, sys.stdin.readline().split())

def LI1():
    return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep='\n')
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    for _ in range(II()):
        s = SI()
        xx = set()
        yy = set()
        ans = 0
        (x, y) = (0, 0)
        for c in s:
            if c == 'N':
                if (x, y) in yy:
                    ans += 1
                else:
                    ans += 5
                yy.add((x, y))
                y += 1
            if c == 'S':
                y -= 1
                if (x, y) in yy:
                    ans += 1
                else:
                    ans += 5
                yy.add((x, y))
            if c == 'E':
                if (x, y) in xx:
                    ans += 1
                else:
                    ans += 5
                xx.add((x, y))
                x += 1
            if c == 'W':
                x -= 1
                if (x, y) in xx:
                    ans += 1
                else:
                    ans += 5
                xx.add((x, y))
        print(ans)
main()

Solution (Python):
t = int(input())
for i in range(t):
    s = input()
    d = {}
    x = 0
    y = 0
    c = 0
    rc = 0
    for j in s:
        m = x
        n = y
        if j == 'N':
            y += 1
        elif j == 'S':
            y -= 1
        elif j == 'E':
            x += 1
        else:
            x -= 1
        if (x, y, m, n) in d or (m, n, x, y) in d:
            rc += 1
        else:
            c += 1
            d[m, n, x, y] = 1
    print(c * 5 + rc)