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 翻译