화산쇄설류

시간 제한1초메모리 제한128 MB

요약
여러 화산의 분출 시각이 주어진 M×N 격자에서 용암이 맨해튼 거리로 번질 때 안전하게 도달할 수 있는 가장 높은 지점과 그곳에 도착하는 최소 시간을 구합니다.
난이도

보통10점 중 7점

유형
최단 경로, 힙, 그래프, 구현
정답자
아직 제출이 없습니다

문제

화산학자 윤재상은 어느 화산섬을 탐사하러 갔다가, 곧 섬에 있는 화산들이 폭발하기 시작할 것이라는 급보와 각 화산의 폭발 시점 정보를 받았다.

섬은 M행 N열의 행렬로 표현된다. 어떤 화산의 위치를 (x, y), 폭발을 시작한 시각을 t라고 하자. t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v) 위치의 지대는 높이와 무관하게 화산쇄설류가 덮친다. 재상이는 빨리 탈출하고 싶다.

  • 재상이는 처음에 X행 Y열에 있다.
  • 재상이는 단위 시간당 상하좌우로 한 칸만 움직일 수 있다.
  • 재상이는 화산이 있는 위치와 화산쇄설류가 뒤덮인 곳으로는 갈 수 없다.

재상이는 화산쇄설류를 피해 되도록 높은 곳으로 피하고 싶고, 되도록 빨리 도달하기를 원한다. 재상이가 화산쇄설류를 피해 도달할 수 있는 가장 높은 고도와, 그 고도에 도달하는 데 걸리는 최소 시간을 구한다.

입력

첫 번째 줄에 정수 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열에 화산이 있는 입력은 주어지지 않는다.

출력

재상이가 도달할 수 있는 최고 높이와 그 높이에 도달할 수 있는 최단 시간을 공백으로 구분하여 출력한다.

예제2

  1. 예제 1

    입력
    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

  2. 예제 2

    입력
    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