편안한 워크숍

H사의 신입사원 A는 입사동기들과 워크숍에서 등산을 가기로 하였습니다. 등산하려는 산의 정보는 N×N 격자로 주어지며 각 칸에 적혀있는 수들은 높이를 의미합니다. A는 입사동기들의 의견을 존중하며 그 중 가장 편안한 등산로를 찾기 원합니다. 입사동기들의 의견을 만족하는 등산로 중 인접한 높이의 차들 간의 최댓값이 최소가 되는 등산로가 가장 편안한 등산로입니다.

다음의 조건들은 입사동기들의 의견입니다.