← 返回题目列表

AtCoder · joi2017ho_c

C. JOIOI王国

中文机器翻译题面 查看原题

配点: 100 点

JOIOI王国是 H 行 W 它具有矩形形状,分为单元列。在JOIOI王国,为了提高行政效率,整个国家都在 2 我们决定将其分为两个区域:JOI 和 IOI。

为了防止区域划分变得过于复杂,我们决定划分区域以满足以下条件:

  • 每个区域都是1 包含三个或更多方块。
  • 每个方格都是2 只是两个区域之一 属于 1 。
  • 哪个区域属于JOI? 2 您可以通过重复移动到边缘彼此相邻的方格来在两个方格之间移动,而无需输入不属于该区域的方格。这同样适用于区域 IOI。
  • 对于每一行和每一列,当您取出属于该行或列的所有单元格时,每个区域中的单元格都是连接的。然而,该行或列中的所有单元格可能属于同一区域。

每个方格都有一个固定的整数,称为高程。划分区域后,预计每个区域内的运动将变得更加活跃。如果一个区域内的高程差异太大,那么移动就会很困难,所以我们要对区域进行划分,使同一区域内的高程差异尽可能小。换句话说,我们要最小化区域JOI中最大和最小高程值之间的差异以及区域IOI中最大和最小高程值之间的差异中的较大者。

課題

给定JOIOI王国中每个方格的高程,编写一个程序,计算满足条件的区域划分时JOI区域中最大和最小高程差值与IOI区域中最大和最小高程差值中较大者的最小值。


入力

从标准输入读取以下输入。

  • 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 以行的形式输出。


制限

所有输入数据满足以下条件。

  • 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 点]

没有其他限制。


入力例 1

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

出力例 1

11

在此输入示例中,您可以如下图所示划分区域。其中,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

入力例 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