C-JOIOI 王国_JOI2017-Final比赛真题

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

为了兼顾表意清楚与简洁，我翻译时脑补了  和 ，所以不要问我为啥原题找不到……

JOIOI王国是一个H行W列的长方形网格，每个 $1 \times1$ 的子网格都是一个正方形的小区块。为了提高管理效率，我们决定把整个国家划分成两个省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个整数，用空格分隔。
输入的所有数的含义见题目描述。

输出描述:

一行，一个整数，表示可能的最小值。

示例1

输入

复制

输出

复制

说明

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

J J J I
J J J I
J J I I
J 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

输出

复制

说明

对于的数据，。
对于另外的数据，。
对于所有数据，对于的数据，。
对于另外的数据，。
对于所有数据，。。

备注:

对于的数据，。
对于另外的数据，。
对于所有数据，。

CC-BY-SA，感谢LOJ分享，译文来自https://loj.ac/problem/2334