P2216 [HAOI2007] Ideal Square

Given an $a \times b$ matrix of integers, find an $n \times n$ square region such that the difference between the maximum and minimum numbers in that region is minimized.

The first line contains 3 integers, representing the values of $a$, $b$, and $n$. From the second line to the $(a+1)$-th line, each line contains $b$ nonnegative integers, representing the numbers at the corresponding positions in the matrix. Adjacent numbers on the same line are separated by a single space.

Output a single integer: the minimal possible difference between the maximum and the minimum among all $n \times n$ square regions in the $a \times b$ matrix.

All numbers in the matrix do not exceed 1,000,000,000. Constraints: For 20% of the testdata, $2 \le a, b \le 100$, $n \le a$, $n \le b$, $n \le 10$. For 100% of the testdata, $2 \le a, b \le 1000$, $n \le a$, $n \le b$, $n \le 100$. Translated by ChatGPT 5