/ 
実行時間制限: 2 sec / メモリ制限: 512 MB
配点 : 800 点
問題文
高橋君の部屋には縦 H 行、横 W 列、 H \times W 個のブロックからなるオブジェがあります。
各ブロックには色がついています。色は英小文字(a-z) で表されます。上から i 個目、左から j 個目のブロックの色は c_{i,j} です。
あまり見栄えが良くないため高橋君はこのオブジェを解体しようとしています。解体作業は以下の操作の繰り返しになります。
- W 個の列のうち一つを選び、その列を一段沈める。その列の一番下にあったブロックは消滅する。
同じ色のブロックは引き寄せ合う力を持つため、この操作にかかるコストは、「選んだ列のブロックと(操作前に)横に隣り合っているブロックで、色が同じもの の個数」になります。
高橋君はこの作業を H \times W 回行うことで全てのブロックを消滅させオブジェを解体します。操作する列の順番をうまく選ぶことによって、解体にかかるコストの総和を最小化してください。
制約
- 1≦H≦300
- 2≦W≦300
- c_{i,j} は英小文字(
a-z)
部分点
- W=3 を満たすデータセットに正解すると、300 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
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
2 3 rrr brg
出力例 1
2
例えば下図のような順で操作するとコストの総和は 2 に出来て、これが最小値です。
入力例 2
6 3 xya xya ayz ayz xaz xaz
出力例 2
0
はじめに真ん中の列を全て沈め、次に左の列を全て沈め、最後に右の列を全て沈めることでコスト0を達成できます。
入力例 3
4 2 ay xa xy ay
出力例 3
0
右の列を一段沈める→左の列を一段沈める→右の段を全て沈める→左の段を全て沈める とすることでコスト0にすることが可能です。
入力例 4
5 5 aaaaa abbba ababa abbba aaaaa
出力例 4
24
入力例 5
7 10 xxxxxxxxxx ccccxxffff cxxcxxfxxx cxxxxxffff cxxcxxfxxx ccccxxfxxx xxxxxxxxxx
出力例 5
130
Score : 800 points
Problem Statement
Mr. Takahashi has in his room an art object with H rows and W columns, made up of H \times W blocks.
Each block has a color represented by a lowercase English letter (a-z).
The color of the block at the i-th row and j-th column is c_{i,j}.
Mr. Takahashi would like to dismantle the object, finding it a bit kitschy for his tastes. The dismantling is processed by repeating the following operation:
- Choose one of the W columns and push down that column one row. The block at the bottom of that column disappears.
Each time the operation is performed, a cost is incurred. Since blocks of the same color have a property to draw each other together, the cost of the operation is the number of the pairs of blocks (p, q) such that:
- The block p is in the selected column.
- The two blocks p and q are horizontally adjacent (before pushing down the column).
- The two blocks p and q have the same color.
Mr. Takahashi dismantles the object by repeating the operation H \times W times to get rid of all the blocks. Compute the minimum total cost to dismantle the object.
Constraints
- 1 ≤ H ≤ 300
- 2 ≤ W ≤ 300
- All characters c_{i,j} are lowercase English letters (
a-z).
Partial Score
- In test cases worth 300 points, W = 3.
Input
The input is given from Standard Input in the following format:
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}
Output
Print the minimum total cost to dismantle the object.
Sample Input 1
2 3 rrr brg
Sample Output 1
2
For example, the total cost of 2 can be achieved by performing the operation as follows and this is the minimum value.
Sample Input 2
6 3 xya xya ayz ayz xaz xaz
Sample Output 2
0
The total cost of 0 can be achieved by first pushing down all blocks of the middle column, then all of the left column, and all of the right column.
Sample Input 3
4 2 ay xa xy ay
Sample Output 3
0
The total cost of 0 can be achieved by the following operations:
- pushing down the right column one row;
- pushing down the left column one row;
- pushing down all of the right column;
- and pushing down all of the left column.
Sample Input 4
5 5 aaaaa abbba ababa abbba aaaaa
Sample Output 4
24
Sample Input 5
7 10 xxxxxxxxxx ccccxxffff cxxcxxfxxx cxxxxxffff cxxcxxfxxx ccccxxfxxx xxxxxxxxxx
Sample Output 5
130