1559번 - 놀라운 미로 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 512 MB | 604 | 106 | 67 | 19.534% |
문제
MxN개의 칸으로 구성된 미로가 있다. 각 칸에는 4개의 인접한 곳으로 이동할 수 있는 문이 있다. 이 4개의 문은 한 번에 한 개만 열리며, A에서 B로 가는 문과 B에서 A로 가는 문은 별개로 작동한다. 문들의 초기 상태는 입력에서 주어지며, 1분에 한 번 시계 방향으로 90도씩 바뀐다.
미로에는 총 K개의 보물상자가 있다. 당신은 1분에 문이 열린 방향으로 한 칸 움직이거나 원하는 방향의 문이 열릴 때까지 기다릴 수 있다.
미로에서 당신이 시작하게 될 위치는 (1, 1)이며, 목표는 모든 보물 상자를 가지고 (M, N)에 도달하는 것이다. 물론 보물 상자를 전부 가지고 있지 않더라도 (M, N)에는 갈 수 있지만 미로를 탈출하기 위해서는 모든 보물 상자를 모아서 가야 한다.
이때 미로를 탈출하기 위한 최소 시간을 구하시오.
입력
입력 데이터는 여러 개의 테스트 케이스로 구성되어 있다. 각각의 입력은 두 정수 M, N(2 ≤ M, N ≤ 100)으로 시작하며, 다음 M개의 줄에는 초기에 문이 열린 방향을 나타내는 N, E, S, W중 하나의 문자가 각 줄에 N개씩 주어진다.
예를 들어 칸의 위치가 (r, c)라면, N, E, S, W는 각각 (r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)로 가는 문이 열려 있다는 것을 의미한다.
이후 보물 상자의 개수인 K(1 ≤ K ≤ 8)가 주어지고, 그 다음 K개의 줄에 각각의 보물상자의 위치를 나타내는 R, C가 주어진다. 한 칸에 여러 개의 보물 상자가 있는 경우는 없으며 보물 상자의 위치가 (1, 1)이거나 (M, N)인 경우도 없다.
마지막 줄의 "0 0"은 입력의 끝을 알린다.
출력
각각의 테스트 케이스에 대해 미로를 탈출하기 위한 최소 시간을 출력한다.
예제 입력 1
2 2 EE NN 1 1 2 0 0
예제 출력 1
2
출처
ICPC > Regionals > North America > Rocky Mountain Regional > Alberta Collegiate Programming Contest > ACPC 2012 F번
- 문제를 번역한 사람: luke0201
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호