#523. [2025-10-28 P1] 选牛

[2025-10-28 P1] 选牛

【题目描述】

n×mn×m 头牛排成一个 nn 行 mm 列的矩阵,第 ii 行第 jj 列的牛身高为 HijH_{ij}。

现在要从中选出一个 k×kk×k 的方阵,使得该方阵中最高的牛与最矮的牛的身高差的绝对值最小。

请你计算并输出这个最小值。

【输入格式】

第一行:包含 33 个整数,分别表示 n,m,kn, m, k 的值。

接下来是一个 nn 行 mm 列的整数矩阵 HH。

【输出格式】

一个整数,表示答案。

【样例输入】

5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2

【样例输出】

1

【数据规模】

矩阵中的所有数都不超过 1,000,000,0001,000,000,000。

2020% 的数据:2≤n,m≤100,k≤n,k≤m,k≤102 ≤ n, m ≤ 100, k ≤ n, k ≤ m, k ≤ 10。

100100% 的数据:2≤a,b≤1000,k≤n,k≤m,k≤1002 ≤ a,b ≤ 1000, k ≤ n, k ≤ m, k ≤ 100。