[백준 시뮬레이션 문제 3190] 뱀

#백준 시뮬레이션 문제 3190번 - 뱀

#난이도 : 중상

N = int(input()) #맵의 가로 세로 길이
K = int(input())

apple_map = []
for k in range(N): #사과의 위치를 기록.
  apple_map.append([0] * N)

body_map = []
for k in range(N): #자기 몸의 위치를 기록.
  body_map.append([0] * N)

for k in range(K):
  y, x = map(int,input().split()) #행,열을 순서대로 받음.
  apple_map[y-1][x-1] = 1


L = int(input()) #방향 변화 횟수
schedule_li = []

for k in range(L):
  t, d = input().split()
  schedule_li.append((int(t),d))



direction_li = [0,1,2,3] #북, 서, 남, 동 순
dx = [0,-1,0,1]
dy = [-1,0,1,0]
d = 3 #동쪽방향으로 시작.
t = 0 #몇초가 지났는지를 셈.
pos_x = 1
pos_y = 1
record_li = [] #몸의 순서를 기록.(사과가 없을시 꼬리부분을 빼고 위함)
record_li.append((pos_x,pos_y))
body_map[pos_y-1][pos_x-1] = 1

while True:

  if pos_x + dx[d] < 1 or pos_x + dx[d] > N : #맵 바깥으로 나가면 중단.
    t+=1
    break
  if pos_y + dy[d] < 1 or pos_y + dy[d] > N : #맵 바깥으로 나가면 중단.
    t+=1
    break
  if body_map[pos_y +dy[d] -1][pos_x + dx[d] -1] == 1: #옮기는 위치에 자신의 몸이 있으면 중단.
    t+=1
    break

 

# 위 조건이 만족안될시 비로소 d 방향으로 이동 가능.
  pos_x += dx[d]
  pos_y += dy[d]


  body_map[pos_y-1][pos_x-1] = 1 #옮긴다음에 머리를 body_map에 표시
  record_li.append((pos_x,pos_y))

  
  if apple_map[pos_y-1][pos_x-1] == 1: #옮긴 곳에 사과가 있으면 다른 몸들은 가만히 있어도 됨.
    apple_map[pos_y-1][pos_x-1] = 0
  else:
    tail_x, tail_y = record_li.pop(0) #옮긴 곳에 사과가 없다면 제일 끝 몸(꼬리)이 사라져야함.
    body_map[tail_y-1][tail_x-1] = 0
    
  t+=1  #위 과정들을 마무리 한 뒤에 시간을 1 더해주고 마무리함. 단 마무리 하기 전에 아래에 schedule_li를 확인하여 방향전환이 필요한지 체크.

  if len(schedule_li) == 0:
    continue
  
  if t == schedule_li[0][0]: 
    if schedule_li[0][1] == "L":
      d = (d+1) % 4  #반시계 방향 전환
    else:
      d = (d-1) % 4  #시계 방향 전환
    schedule_li.pop(0)
  
    
print(t)

 

#시간 복잡도 : O(NL)

#최악의경우는 뱀의길이가 1이면서 계속해서 맵을 뺑뺑 도는 경우이기 때문.