레이팅 미적용농부 존(Farmer John)의 들판 중 하나는 유난히 언덕이 많아서, 존은 그 위를 몰고 다닐 새 트랙터를 구입하려 한다. 들판은 음이 아닌 정수 고도로 이루어진 N x N 격자 (1 <= N <= 500)로 표현된다. 한 격자 칸에서 고도 차가 D인 인접 칸(북, 동, 남, 서로 한 칸)으로 이동할 수 있는 트랙터는 정확히 D 단위의 돈이 든다.
FJ는 들판의 어떤 격자 칸에서 출발하여, 들판의 격자 칸 중 절반 이상을 트랙터로 성공적으로 돌아다닐 수 있을 만큼 충분한 값의 트랙터를 사고 싶어 한다 (들판의 총 칸 수가 홀수이면 절반을 올림한 수 이상의 칸을 방문하고 싶어 한다). 이 작업이 가능한 트랙터를 사는 데 필요한 최소 비용을 계산하는 것을 도와주자.
첫째 줄: N의 값.
둘째 줄부터 1+N번째 줄까지: 각 줄에 FJ의 들판의 한 행을 나타내는, 공백으로 구분된 N개의 음이 아닌 정수(각각 최대 100만)가 주어진다.
FJ의 들판의 절반 이상을 돌아다닐 수 있는 트랙터의 최소 비용.
tractor.in · 출력을 쓸 파일 tractor.out5
0 0 0 3 3
0 0 0 0 3
0 9 9 3 3
9 9 9 3 3
9 9 9 9 33Output details: A tractor of cost 3 can move between elevation 0 and elevation 3, visiting the zero block and the elevation-3 block, together at least half the farm.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > February > Silver