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 ``` - - - - - -