JOIOI 王国 (Kingdom of JOIOI)

题意翻译

### 题目描述 JOIOI 王国是一个 $H$ 行 $W$ 列的长方形网格,每个 $1 \times 1$ 的子网格都是一个正方形的小**区块**。为了提高管理效率,我们决定把整个国家划分成两个省 JOI 和 IOI。 我们定义,两个同省的区块**互相连接**,意为从一个区块出发,不用穿过任何一个不同省的区块,就可以移动到另一个区块。有公共边的区块间可以任意移动。 我们不希望划分得过于复杂,因此划分方案需满足以下条件: - 区块不能被分割为两半,一半属 JOI 省,一半属 IOI 省。 - 每个省必须包含至少一个区块,每个区块也必须属于且只属于其中一个省。 - 同省的任意两个小区块互相连接。 - 对于每一行/列,如果我们将这一行/列单独取出,这一行/列里同省的任意两个区块互相连接。这一行/列内的所有区块可以全部属于一个省。 现给出所有区块的海拔,第 $i$ 行第 $j$ 列的区块的海拔为 $A_{i,j}$ 。设 JOI 省内各区块海拔的极差(最大值减去最小值)为 $R_{JOI}$,IOI 省内各区块海拔的极差为 $R_{IOI}$ 。在划分后,省内的交流有望更加活跃。但如果两个区块的海拔差太大,两地间的交通会很不方便。 因此,理想的划分方案是 $\max(R_{JOI},R_{IOI})$ 尽可能小。 你的任务是求出 $\max(R_{JOI},R_{IOI})$ 至少为多大。 ### 输入格式 第一行,两个整数 $H,W$,用空格分隔。 在接下来的 $H$ 行中,第 $i$ 行有 $W$ 个整数 $A_{i,1},A_{i,2}, \cdots ,A_{i,W}$,用空格分隔。 输入的所有数的含义见题目描述。 ### 输出格式 一行,一个整数,表示 $\max(R_{JOI},R_{IOI})$ 可能的最小值。 ### 数据范围 对于 $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$)。

题目描述

[problemUrl]: https://atcoder.jp/contests/joi2017ho/tasks/joi2017ho_c

输入输出格式

输入格式


標準入力から以下の入力を読み込め. - $ 1 $ 行目には,$ 2 $ 個の整数 $ H,\ W $ が空白を区切りとして書かれている.これらは,JOIOI 国が $ H $ 行 $ W $ 列のマスに区切られた長方形の形をしていることを表す. - 続く $ H $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ H $) には,$ W $ 個の整数 $ A_{i,\ 1},\ A_{i,\ 2},\ \ldots,\ A_{i,\ W} $ が空白を区切りとして書かれている.これは,JOIOI 王国の上から $ i $ 行目,左から $ j $ 列目 ($ 1\ \leqq\ j\ \leqq\ W $) の標高が $ A_{i,\ j} $ であることを表す.

输出格式


標準出力に,条件を満たすように地域の分割をした際の,地域 JOI の中での標高の最大値と最小値の差と,地域 IOI の中での標高の最大値と最小値の差のうち,大きい方の値の最小値を $ 1 $ 行で出力せよ. - - - - - -

输入输出样例

输入样例 #1

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

输出样例 #1

11

输入样例 #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

说明

### 課題 JOIOI 王国の各マスの標高が与えられたとき,条件を満たすように地域の分割をした際の,地域 JOI の中での標高の最大値と最小値の差と,地域 IOI の中での標高の最大値と最小値の差のうち,大きい方の値の最小値を求めるプログラムを作成せよ. - - - - - - ### 制限 すべての入力データは以下の条件を満たす. - $ 2\ \leqq\ H\ \leqq\ 2\,000 $. - $ 2\ \leqq\ W\ \leqq\ 2\,000 $. - $ 1\ \leqq\ A_{i,\ j}\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ H $,$ 1\ \leqq\ j\ \leqq\ W $). ### 小課題 1 \[15 点\] 以下の条件を満たす. - $ H\ \leqq\ 10 $. - $ W\ \leqq\ 10 $. ### 小課題 2 \[45 点\] 以下の条件を満たす. - $ H\ \leqq\ 200 $. - $ W\ \leqq\ 200 $. ### 小課題 3 \[40 点\] 追加の制限はない. - - - - - - ### Sample Explanation 1 この入力例では,例えば下の図のように地域を分割すればよい.ここで,J は地域 JOI,I は地域 IOI を表す. ``` J J J I J J J I J J I I J I I I ``` ここで,例えば次のような分割は,左から $ 3 $ 列目において地域 IOI がひとつながりになっていないため,条件を満たす分割ではない. ``` J J I I J J J I J J J I J I I I ``` - - - - - -