AT_joi2018_yo_c 幹線道路 (Trunk Road)

JOI 市由 $H$ 条东西方向的道路和 $W$ 条南北方向的道路组成，这些道路将城市划分成了一个棋盘格。每两条相邻道路之间的距离为 $1$。现在，JOI 市需要从这些 $H+W$ 条道路中，分别选出一条东西方向的道路和一条南北方向的道路，共计 $2$ 条作为主干道。 从北向南第 $i$ 条道路与从西向东第 $j$ 条道路的交点称为交叉点 $(i, j)$。交叉点 $(i, j)$ 到北向南第 $m$ 条道路的距离为 $|i-m|$，到西向东第 $n$ 条道路的距离为 $|j-n|$。此外，交叉点 $(i, j)$ 附近住有 $A_{i,j}$ 人。 请你选择 $2$ 条主干道，使得 JOI 市所有居民到最近的主干道的距离之和最小。输出这个最小值。

输入通过标准输入给出，格式如下： > $H$ $W$ > $A_{1,1}$ $A_{1,2}$ ... $A_{1,W}$ > $A_{2,1}$ $A_{2,2}$ ... $A_{2,W}$ > $\vdots$ > $A_{H,1}$ $A_{H,2}$ ... $A_{H,W}$

输出 JOI 市所有居民到最近主干道的距离之和的最小值。

## 限制条件 - $2 \leq H \leq 25$ - $2 \leq W \leq 25$ - $0 \leq A_{i,j} \leq 100$（$1 \leq i \leq H$，$1 \leq j \leq W$） ## 子任务 1 [10 分] - $A_{i,j} = 1$（$1 \leq i \leq H$，$1 \leq j \leq W$） ## 子任务 2 [90 分] - 无其他限制。 ## 样例解释 1 例如，选择北向南第 $2$ 条道路和西向东第 $1$ 条道路作为主干道即可。 ## 样例解释 2 例如，选择北向南第 $3$ 条道路和西向东第 $2$ 条道路作为主干道即可。 由 ChatGPT 4.1 翻译