AT_codefestival_2016_qualC_d Friction

高桥君的房间里有一个由 $H$ 行 $W$ 列、共 $H \times W$ 个方块组成的物体。每个方块都有颜色，颜色用小写英文字母（`a`-`z`）表示。从上往下第 $i$ 行，从左往右第 $j$ 列的方块颜色为 $c_{i,j}$。 由于这个物体看起来不太美观，高桥君打算将其拆解。拆解操作如下： - 从 $W$ 列中选择一列，将该列下沉一格。该列最底部的方块会消失。 由于相同颜色的方块之间有吸引力，这个操作的代价为“所选列的方块与（操作前）左右相邻方块中，颜色相同的方块数量”。 高桥君需要通过 $H \times W$ 次操作将所有方块消除并拆解这个物体。请通过合理选择每次操作的列的顺序，使得拆解的总代价最小。

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

输出拆解所需总代价的最小值。

## 限制条件 - $1 \leq H \leq 300$ - $2 \leq W \leq 300$ - $c_{i,j}$ 为小写英文字母（`a`-`z`） ## 部分得分 - 对于 $W=3$ 的数据集，答对可得 $300$ 分。 ## 样例解释 1 例如，按照下图的顺序操作，总代价可以做到 $2$，这是最小值。  ## 样例解释 2 先将中间的列全部下沉，再将左边的列全部下沉，最后将右边的列全部下沉，可以实现总代价 $0$。 ## 样例解释 3 先将右边的列下沉一格→左边的列下沉一格→右边的列全部下沉→左边的列全部下沉，这样也可以实现总代价 $0$。 由 ChatGPT 4.1 翻译