RiseOJ – 크로스컨트리 스키

설명

겨울 무림픽의 크로스컨트리 스키 코스는 고도로 이루어진 M x N 격자 (1 <= M,N <= 500)로 표현되며, 각 고도는 0 .. 1,000,000,000 범위이다.

이 격자의 일부 칸은 코스의 경유지로 지정되어 있다. 주최 측은 코스 전체에 난이도 등급 D를 부여하여, 인접한 칸 사이의 고도 차이의 절댓값이 D 이하일 때에만 칸에서 칸으로 스키를 타고 이동하는 것을 반복하여, 어느 경유지에서든 다른 어느 경유지로도 소가 도달할 수 있게 하려고 한다. 두 칸은 한 칸이 다른 칸의 바로 북쪽, 남쪽, 동쪽, 서쪽에 있을 때 인접하다. 코스의 난이도 등급은 이러한 방식으로 모든 경유지가 서로 도달 가능하게 되는 D의 최솟값이다.

제약

입력 형식

첫째 줄에 정수 M과 N이 주어진다.

둘째 줄부터 1+M번째 줄까지, 이 M개의 줄 각각에 N개의 정수 고도가 주어진다.

2+M번째 줄부터 1+2M번째 줄까지, 이 M개의 줄 각각에 0 또는 1인 값 N개가 주어지며, 1은 그 칸이 경유지임을 나타낸다.

출력 형식

코스의 난이도 등급(모든 경유지가 서로 도달 가능하게 되는 D의 최솟값)을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 ccski.in · 출력을 쓸 파일 ccski.out

예제 1

입력

3 5
20 21 18 99 5
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1

출력

설명

Output details: If D = 21 the three waypoints are mutually reachable; for D < 21 the upper-right waypoint is isolated.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > January > Silver

올림피아드 > USACO > 2013-2014 > January > Silver

태그

JudgeUSACO

크로스컨트리 스키

평가 및 의견

풀이 제출