배열에서 이동

n × n 크기의 배열이 있다. (1, 1) 칸에서 시작해 (n, n) 칸까지 이동하려고 한다. 한 번에 위, 아래, 왼쪽, 오른쪽으로 인접한 칸 중 하나로만 이동할 수 있다.

이동 경로에 포함된 칸들의 값 중 최댓값과 최솟값의 차이를 생각하자. 가능한 경로 중에서 이 차이가 가장 작아지는 값을 구하시오.

첫째 줄에 정수 n(2 ≤ n ≤ 100)이 주어진다. 이어지는 n개의 줄에는 배열의 값이 한 줄에 n개씩 주어진다. 각 값은 0 이상 200 이하의 정수이다.

가능한 경로에서 이동 중 만나는 값들의 최댓값과 최솟값의 차이 중 최솟값을 출력한다.