AT_joig2023_e.運河 (Canal)

JOIG 王国呈一个被划分为 $H$ 行 $W$ 列网格的长方形。在第 $i$ 行（$1 \leq i \leq H$），第 $j$ 列（$1 \leq j \leq W$）的格子称为格子 $(i,j)$。

每个格子都有一个称为“海拔”的整数。格子 $(i,j)$ 的海拔为 $A_{i,j}$。

JOIG 王国计划修建一条纵贯全国的运河。运河的修建方式如下：

• 选择一个整数 $k$（$1 \leq k < W$），在从左往右第 $k$ 列与第 $k+1$ 列之间，从王国的最上端到最下端修建一条纵贯的运河。

在不跨越运河的前提下，可以多次移动到与当前格子边相邻且海拔相同的格子。能够相互到达的这类格子集合称为平地。为了便于国土管理，应选择一个运河的修建位置，使修建后国内的平地区块数尽量少。

请编写程序，给定 JOIG 王国的地形信息，求修建运河后国内可能的最小平地区块数。

输入如下格式：

$H$ $W$
$A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\cdots$ $A_{H,W}$

输出修建运河后 JOIG 王国内可能的最小平地区块数。

小任务

1.（6 分）$H = 1$。
2.（20 分）$H \leq 2$。
3.（27 分）$H \leq 200$，$W \leq 200$。
4.（47 分）没有额外限制。

样例解释 1

当 $k=3$ 时修建运河，JOIG 王国会被分为如下 4 个平地区块：

• 包含格子 $(1,1)$、$(1,2)$、$(1,3)$、$(2,3)$、$(3,2)$、$(3,3)$ 的平地。
• 包含格子 $(2,1)$、$(2,2)$、$(3,1)$、$(4,1)$、$(4,2)$、$(4,3)$ 的平地。
• 包含格子 $(1,4)$、$(2,4)$、$(3,4)$ 的平地。
• 包含格子 $(4,4)$ 的平地。

无法使 JOIG 王国内的平地区块数小于 4，因此应输出 4。

此输入满足小任务 3、4 的限制。

样例解释 2

当 $k=1$ 时修建运河，JOIG 王国被分为 8 个平地区块。无法使平地区块数小于 8，因此输出 8。

此输入满足小任务 3、4 的限制。

样例解释 3

此输入满足所有小任务的限制。

样例解释 4

此输入满足小任务 2、3、4 的限制。

数据范围

• $H \geq 1$。
• $W \geq 2$。
• $H \times W \leq 500\,000$。
• $1 \leq A_{i,j} \leq 10^9$（$1 \leq i \leq H$，$1 \leq j \leq W$）。
• 所有输入均为整数。

由 ChatGPT 5 翻译