배열에서 이동
시간 제한1초메모리 제한256 MB
n x n 격자에서 왼쪽 위부터 오른쪽 아래까지 이동하는 경로 중 경로 상 최댓값과 최솟값의 차이를 최소화하는 문제입니다.
문제
n × n 크기의 배열이 있다. (1, 1) 칸에서 시작해 (n, n) 칸까지 이동하려고 한다. 한 번에 위, 아래, 왼쪽, 오른쪽으로 인접한 칸 중 하나로만 이동할 수 있다.
이동 경로에 포함된 칸들의 값 중 최댓값과 최솟값의 차이를 생각하자. 가능한 경로 중에서 이 차이가 가장 작아지는 값을 구하시오.
입력
첫째 줄에 정수 n(2 ≤ n ≤ 100)이 주어진다. 이어지는 n개의 줄에는 배열의 값이 한 줄에 n개씩 주어진다. 각 값은 0 이상 200 이하의 정수이다.
출력
가능한 경로에서 이동 중 만나는 값들의 최댓값과 최솟값의 차이 중 최솟값을 출력한다.