#2334. 「JOI 2017 Final」JOIOI 王国

内存限制:256 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

题目译自 JOI 2017 Final T3「 JOIOI 王国 / The Kingdom of JOIOI

为了兼顾表意清楚与简洁,我翻译时脑补了 R_{\text{JOI}} R_{\text{IOI}} ,所以不要问我为啥原题找不到……

JOIOI 王国是一个 H W 列的长方形网格,每个 1\times 1 的子网格都是一个正方形的小区块。为了提高管理效率,我们决定把整个国家划分成两个省 JOI 和 IOI 。

我们定义,两个同省的区块互相连接,意为从一个区块出发,不用穿过任何一个不同省的区块,就可以移动到另一个区块。有公共边的区块间可以任意移动。
我们不希望划分得过于复杂,因此划分方案需满足以下条件:

  • 区块不能被分割为两半,一半属 JOI 省,一半属 IOI 省。
  • 每个省必须包含至少一个区块,每个区块也必须属于且只属于其中一个省。
  • 同省的任意两个小区块互相连接。
  • 对于每一行/列,如果我们将这一行/列单独取出,这一行/列里同省的任意两个区块互相连接。这一行/列内的所有区块可以全部属于一个省。

现给出所有区块的海拔,第 i 行第 j 列的区块的海拔为 A_{i,j} 。设 JOI 省内各区块海拔的极差(最大值减去最小值) 为 R_{\text{JOI}} ,IOI 省内各区块海拔的极差为 R_{\text{IOI}} 。在划分后,省内的交流有望更加活跃。但如果两个区块的海拔差太大,两地间的交通会很不方便。 因此,理想的划分方案是 \max(R_{\text{JOI}}, R_{\text{IOI}}) 尽可能小。
你的任务是求出 \max(R_{\text{JOI}}, R_{\text{IOI}}) 至少为多大。

输入格式

第一行,两个整数 H,W ,用空格分隔。
在接下来的 H 行中,第 i 行有 W 个整数 A_{i,1}, A_{i, 2}, \ldots, A_{i, W} ,用空格分隔。
输入的所有数的含义见题目描述。

输出格式

一行,一个整数,表示 \max(R_{\text{JOI}}, R_{\text{IOI}}) 可能的最小值。

样例

样例输入 1

4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10

样例输出 1

11

样例解释 1

在这组样例中,一种理想方案长这样。下图中, J 表示该区块属于 JOI 省, I 表示该区块属于 IOI 省。

J J J I
J J J I
J J I I
J I I I

注意下述方案不符合第四条原则,将第三列单独取出时,两个 I 不能互相连接。

J J I I
J J J I
J J I I
J I I I

样例输入 2

8 6
23 23 10 11 16 21
15 26 19 28 19 20
25 26 28 16 15 11
11 8 19 11 15 24
14 19 15 14 24 11
10 8 11 7 6 14
23 5 19 23 17 17
18 11 21 14 20 16

样例输出 2

18

数据范围与提示

对于 15\% 的数据, H, W\leqslant 10
对于另外 45\% 的数据, H, W\leqslant 200
对于所有数据, 2\leqslant H, W\leqslant 2000, A_{i,j}\leqslant 10^9(1\leqslant i\leqslant H, 1\leqslant j\leqslant W)