뱀

• 시키는대로 구현해주면 되는 문제.
• 뱀이 차지하고 있는 좌표들를 덱에 저장해서, 뱀이 머리의 위치가 덱의 맨 앞에, 꼬리의 위치가 덱의 맨 뒤에 저장되도록 하면, 뱀의 이동을 덱의 맨 뒤의 원소를 제거하고 맨앞에 이동하는 새 좌표를 추가하는 식으로 O(1)에 처리할수 있다.
• 마찬가지로 2차원 배열에도 뱀의 차지하고 있는 좌표들을 저장한다면, 새로 이동한 곳에 뱀에 몸통이 있어서 충돌하는지 여부를 O(1)에 체크할수 있다.
• X초동안 시뮬레이션 하고, 매초마다 O(1)의 계산이 필요하므로 총 시간복잡도는 O(X)

"""Solution code for "BOJ 3190. 뱀".

- Problem link: https://www.acmicpc.net/problem/3190
- Solution link: http://www.teferi.net/ps/problems/boj/3190

Tags: [Implementation]
"""

import collections

APPLE = 'A'
SNAKE = 'S'
EMPTY = 'E'
DELTAS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
INF = float('inf')


def main():
    N = int(input())
    grid = [[EMPTY] * N for _ in range(N)]
    K = int(input())
    for _ in range(K):
        apple_r, apple_c = [int(x) for x in input().split()]
        grid[apple_r - 1][apple_c - 1] = APPLE
    L = int(input())
    turns = []
    for _ in range(L):
        X, C = input().split()
        turns.append((int(X), C))

    turns.append([INF, 'X'])
    r, c = 0, 0
    grid[r][c] = SNAKE
    queue = collections.deque([(r, c)])
    direction = 0
    dr, dc = DELTAS[direction]
    t = 0
    for X, C in turns:
        while t < X:
            t += 1
            r, c = r + dr, c + dc
            if not (0 <= r < N and 0 <= c < N) or grid[r][c] == SNAKE:
                break
            if grid[r][c] == EMPTY:
                tail_r, tail_c = queue.popleft()
                grid[tail_r][tail_c] = EMPTY
            grid[r][c] = SNAKE
            queue.append((r, c))
        else:
            direction = (direction + (1 if C == 'D' else -1)) % 4
            dr, dc = DELTAS[direction]
            continue
        break

    print(t)