COCI 2012/2013 - Contest 5- 로봇 충전하기 (BAKTERIJE) > 문제은행 : 정보올림피아드&알고리즘




1735 : 로봇 충전하기 (BAKTERIJE)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
1 회   
시도횟수
3 회   

문제

N행 M열의 격자에 K개의 로봇이 있다. 각 로봇은 내장된 정보에 따라(각 로봇마다 다르다) 다음과 같은 방식으로 움직인다.




1) 로봇은 자신이 위치한 격자의 X값을 읽어 들인다.

2) 시계방향으로 90도 회전하는 것을 X번 한다.

3) 만약 로봇이 격자 밖을 바라보고 있다면 180도 회전한다.

4) 자신이 바라보는 방향으로 한 칸 움직인다.

 


로봇은 회전을 엄청 빨리 할 수 있기 때문에 로봇이 회전하는 시간은 무시할 수 있다. 

한편 로봇이 한 칸 움직이는 데 걸리는 시간은 1초이다.


로봇의 주인인 제노는 K개의 로봇들의 배터리 잔량이 부족한 것을 깨달았다! 

하지만 로봇이 작동 중일 때에는 로봇을 조종할 수 없게 설계되었기 때문에 로봇들이 알아서 충전기로 와야 한다. 

그러나 충전기는 K개의 로봇이 모두 올 때만 작동한다.


제노는 충전기도 비싼 돈으로 사들인 만큼 성능이 엄청나기 때문에, 충전을 시작하면 정확히 1초 만에 로봇이 충전이 된다.


이 때, 제노의 로봇이 모두 충전될 때까지 걸리는 시간을 구하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에는 N, M, K가 주어진다. (3 ≤ N, M ≤ 50, 1 ≤ K ≤ 5)

두 번째 줄에는 충전기의 행 번호와 열 번호가 주어진다. 

세 번째 줄부터는 K개의 로봇에 대한 정보가 주어진다.

 

각 로봇에 대하여, 첫 번째 줄에는 처음 위치(행 번호와 열 번호)와 로봇의 방향(U - 위, R - 오른쪽, D - 아래, L - 왼쪽)이 주어진다.

두 번째 줄부터 N개의 줄에는 각 격자의 X값이 공백 없이 주어진다. X값은 0~9 사이의 정수이다.


출력형식

제노의 로봇이 모두 충전될 때까지 걸리는 시간을 출력한다. 만약 충전을 영영 못 한다면 -1을 출력한다.

입력 예

3 3 1
2 2
1 1 R
010
000
000

출력 예

3

입력 예

3 4 2
2 2
3 4
2327
6009
2112
3 2 
1310
2101
1301

출력 예

8


CRT

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP