시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1378 | 347 | 234 | 23.031% |
화산학자 윤재상은 어느 화산섬을 탐사하러 갔다가 곧 섬에 있는 화산들이 곧 폭발하기 시작할 것이라는 급보와 각 화산의 폭발 시점 정보를 받았다.
섬은 M행 N열의 행렬로 표현된다. 어떤 화산의 위치를 (x, y), 폭발을 시작한 시각을 t 라고 하자. t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다. 재상인 빨리 탈출을 하고싶다.
재상이는 화산쇄설류를 피해서 되도록 가장 높은 곳으로 피하고 싶고, 되도록 가장 빨리 도달하기를 원한다. 재상이가 화산쇄설류를 피해서 도달할 수 있는 가장 높은 고도와, 그 고도까지 도달하는데 걸리는 최소 시간을 구한다.
첫 번째 줄에 정수 M, N, V이 공백으로 구분되어 주어진다. (1 ≤ M, N ≤ 100, 1 ≤ V ≤ min(5,000, M×N))
그 다음 줄에 X, Y가 공백으로 구분되어 주어진다. (1 ≤ X ≤ M, 1 ≤ Y ≤ N)
그 다음 줄부터 M개의 줄마다 N개의 공백으로 구분된 수들이 주어진다. i행 j열의 값은 (i, j) 지대의 고도 hij 를 나타낸다. (0 ≤ hij ≤ 10,000)
그 다음 줄부터 V개의 줄이 주어진다. i번째 줄에 xi, yi, ti가 공백으로 구분되어 주어진다. 이 수들은 i번째 화산의 위치 (xi, yi,)와 화산의 분출시각 ti를 의미한다. (1 ≤ xi ≤ M, 1 ≤ yi ≤ N, 0 ≤ ti ≤ 200)
위치, 시간, 고도 수치들은 모두 정수이다. X행 Y열에 화산이 있는 입력은 주어지지 않는다.
재상이가 도달할 수 있는 최고 높이와 그 높이에 도달할 수 있는 최단 시간을 공백을 구분하여 출력한다.
8 8 8 5 8 58 34 30 23 12 44 18 30 4 62 26 42 64 39 44 25 64 34 6 10 0 25 46 34 42 3 62 48 20 25 25 41 35 30 4 33 35 39 41 38 7 43 37 3 0 25 20 23 20 59 18 43 1 14 16 11 17 50 12 19 59 48 7 4 4 5 4 2 6 4 5 1 2 8 8 3 5 6 2 8 2 2 5 2 1 3 5 2
46 3
8 8 8 1 8 7 9 1 60 5 49 19 27 38 25 18 1 52 43 22 0 20 35 39 43 10 17 34 43 21 50 13 34 64 57 24 48 64 18 14 40 62 11 3 58 64 22 60 15 5 16 59 8 1 61 19 9 13 53 50 14 5 30 7 13 44 25 15 63 2 3 2 2 7 2 4 6 2 2 8 2 5 8 2 4 7 2 5 2 5 6 3 1
49 2
University > 서강대학교 > 2018 Sogang Programming Contest > Champion C번