AT_codefestival_2016_qualC_d Friction

[problemUrl]: https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_d 高橋君の部屋には縦 $ H $ 行、横 $ W $ 列、 $ H\ \times\ W $ 個のブロックからなるオブジェがあります。 各ブロックには色がついています。色は英小文字(`a`-`z`) で表されます。上から $ i $ 個目、左から $ j $ 個目のブロックの色は $ c_{i,j} $ です。 あまり見栄えが良くないため高橋君はこのオブジェを解体しようとしています。解体作業は以下の操作の繰り返しになります。 - $ W $ 個の列のうち一つを選び、その列を一段沈める。その列の一番下にあったブロックは消滅する。 同じ色のブロックは引き寄せ合う力を持つため、この操作にかかるコストは、「選んだ列のブロックと(操作前に)横に隣り合っているブロックで、色が同じもの の個数」になります。 高橋君はこの作業を $ H\ \times\ W $ 回行うことで全てのブロックを消滅させオブジェを解体します。操作する列の順番をうまく選ぶことによって、解体にかかるコストの総和を最小化してください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ c_{1,1}c_{1,2} $..$ c_{1,W} $ $ c_{2,1}c_{2,2} $..$ c_{2,W} $ $ : $ $ c_{H,1}c_{H,2} $..$ c_{H,W} $

解体にかかるコストの総和の最小値を出力せよ。

### 制約 - $ 1≦H≦300 $ - $ 2≦W≦300 $ - $ c_{i,j} $ は英小文字(`a`-`z`) ### 部分点 - $ W=3 $ を満たすデータセットに正解すると、$ 300 $ 点が与えられる。 ### Sample Explanation 1 例えば下図のような順で操作するとコストの総和は $ 2 $ に出来て、これが最小値です。 !\[c116dab4c0a2f42759c6476d95330a37.png\](https://atcoder.jp/img/code-festival-2016-qualc/c116dab4c0a2f42759c6476d95330a37.png) ### Sample Explanation 2 はじめに真ん中の列を全て沈め、次に左の列を全て沈め、最後に右の列を全て沈めることでコスト$ 0 $を達成できます。 ### Sample Explanation 3 右の列を一段沈める→左の列を一段沈める→右の段を全て沈める→左の段を全て沈める とすることでコスト$ 0 $にすることが可能です。