Space-A
면접 대비시간 제한1초메모리 제한1024 MB
고정된 R, U, X 이동 순서에서 일부 명령을 골라 로봇이 도달할 수 있는 점의 개수를 구합니다.
문제
아주국의 핵심 우주 개발 프로젝트인 Space-A를 맡은 선우는 탐사 로봇으로 새로 발견된 미지의 행성을 탐사한다.
미지의 행성에서 탐사할 공간은 2차원 평면으로 나타낼 수 있다. 로봇은 처음에 에 있다. 로봇은 다음 세 가지 이동을 할 수 있다.
R: 좌표가 증가하는 방향으로 한 칸 움직인다.U: 좌표가 증가하는 방향으로 한 칸 움직인다.X: , 좌표가 모두 증가하는 대각선 방향으로 한 칸 움직인다.
로봇의 이동 명령 순서는 사전에 정해져 있다. 선우는 정해진 명령 중 몇 개를 임의로 골라 로봇을 이동시키려 한다. 예를 들어 이동 명령 순서가 URURR이라고 하자. 첫 번째, 세 번째, 네 번째 명령을 골라 로봇을 이동시키면 로봇은 UUR 순서로 이동한다.
선우가 탐사해야 하는 행성의 지점 정보가 주어질 때, 로봇의 이동을 적절히 골라 탐사할 수 있는 지점의 개수를 구하라.
한 번의 이동으로 여러 지점을 방문하는 것이 아니라, 시작 지점에서 도달할 수 있는 지점의 수를 구하는 것임에 유의하라. 또한 로봇의 시작 위치는 언제나 탐사가 가능하다.
입력
첫 번째 줄에 로봇의 이동 횟수 이 주어진다.
두 번째 줄에는 사전에 정해진 로봇의 이동 명령 순서가 길이 인 문자열로 주어진다.
세 번째 줄에 로봇을 이용해 탐사하고 싶은 지점의 수 가 주어진다.
네 번째 줄부터 줄에 걸쳐 탐사해야 하는 지점의 좌표와 좌표가 공백으로 구분되어 주어진다.
같은 좌표는 두 번 입력되지 않는다.
출력
탐사해야 하는 지점 중 로봇의 이동을 적절히 골라 탐사할 수 있는 지점의 개수를 출력하시오.