문제
개구리 왕눈이는 천신마고끝에 여자친구 아로미가 갇혀있는 심술장이 메기의 감옥에 도착했다.
이제 감옥으로부터 아로미를 업고 탈출 지도를 따라 안전지역까지 가야한다.
물속은 너무도 위험하여 연못에 떠있는 식물의 잎을 밟고 점프하여 이동하는데
한번 밟은 잎은 연못 아래로 가라 앉는다.
왕눈이는 한 위치 (x, y) 로 부터 아래 네 가지 방법 중 한 가지로만 뛴다.
그런데 그 방향에 식물의 잎이 없다면 그 자리에 가만히 한 번 쉰다.
A 방향 뛰기 (x + P, y + P) : P 는 양의 정수이다.
B 방향 뛰기 (x + P, y - P) : P 는 양의 정수이다.
C 방향 뛰기 (x - P, y + P) : P 는 양의 정수이다.
D 방향 뛰기 (x - P, y - P) : P 는 양의 정수이다.
왕눈이와 아로미의 초기위치와 탈출 지도가 주어질 때,
마지막으로 도착한 안전지역의 좌표를 구하는 프로그램을 작성하시오.
입력
첫 행에 식물의 수 N과 점프의 수 K 가 주어진다.( 1 <= N, K <= 100,000)
두 번째 행에 탈출지도에 적힌 K개의 점프방향이 주어진다.
각 점프방향은 'A', 'B', 'C', 'D' 4가지 중 하나이다.
세 번째 행부터 N개의 행에는 식물의 좌표 x, y가 주어진다.( 0 <= x, y <= 1,000,000,000)
식물의 좌표 중 첫 위치는 왕눈이와 아로미의 초기위치이다.
출력
마지막으로 도착한 안전지역의 좌표를 출력한다.
예제 #1
7 5
ACDBB
5 6
8 9
4 13
1 10
7 4
10 9
3 7
7 4
예제 #2
6 12
AAAAAABCCCDD
1 1
2 2
3 3
4 4
5 3
6 2
5 3
출처
COCI 2007/2008 Contest #6 5번
로그인해야 코드를 작성할 수 있어요.