시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1233 | 286 | 195 | 23.214% |
화물차가 출발지 창고에서 짐을 싣고 배송지 창고까지 짐을 운반하려고 한다. 이 도시의 도로망을 나타낸 지도의 예는 다음과 같다.
#A##0##1# .#..#..#. .#..#..#. .###2#.B.
도로망에서 차들은 동, 서, 남, 북의 방향으로만 이동할 수 있고, 지도의 각 문자는 다음과 같은 의미를 가진다.
차량의 이동은 다음과 같은 방식으로 분석된다.
출발지 창고에서 배송지 창고까지 최단 경로를 구하는 프로그램을 작성하시오.
입력은 여러 개의 테스트 케이스로 구성된다. 각 테스트 케이스의 첫째 줄에는 두 개의 정수 m과 n이 주어진다, 여기서 m은 지도를 나타내는 행렬의 행의 크기이고 n은 열의 크기이다(2 ≤ m, n ≤ 20).
그 다음 m개의 줄에는 각 줄마다 n개의 문자가 주어진다. 각 문자는 지도를 구성하는 문자인 '#', '.', 'A', 'B', [0-9]로 구성된다.
그 다음 줄부터는 각 교차로에 대한 정보가 주어진다. 교차로 번호가 0인 것부터 오름차순으로 한 줄에 하나씩 주어진다. 각 줄에는 교차로 번호 i와 '-' 또는 '|', 그 다음으로 두 개의 정수 ai와 bi (1 ≤ ai, bi ≤ 20) 가 빈칸을 사이에 두고 주어진다, 여기서 '-'는 신호등이 초기에 동서 방향의 신호가 켜짐을 나타내고, '|'는 남북 방향의 신호가 켜짐을 나타낸다. ai와 bi는 각각 동서 방향 신호가 켜 있는 시간과 남북 방향 신호가 켜 있는 시간을 나타낸다.
각 테스트 케이스 사이에는 빈 줄 하나가 들어 있고, 두 개의 0으로 시작되는 테스트 케이스는 입력의 끝을 나타낸다. 테스트 케이스는 20개를 넘지 않는다고 가정해도 된다.
각 테스트 케이스에 대해, 한 줄에 한 개의 정수를 출력한다. 이 정수는 출발지 창고에서 배송지 창고까지 차량으로 이동하는 데 걸리는 최소 시간이다. 만일 차량이 배송지 창고까지 도달할 수 없으면 "impossible"을 출력한다.
3 4 A##B #..# #### 4 9 #A##0##1# .#..#..#. .#..#..#. .###2#.B. 0 - 1 17 1 | 3 5 2 - 2 4 2 2 A. .B 0 0
3 17 impossible
University > Stanford Local ACM Programming Contest > SLPC 2008 C번