Score : 800 points
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:
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:
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.
a
-z
).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}
Print the minimum total cost to dismantle the object.
2 3 rrr brg
2
For example, the total cost of 2 can be achieved by performing the operation as follows and this is the minimum value.
6 3 xya xya ayz ayz xaz xaz
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.
4 2 ay xa xy ay
0
The total cost of 0 can be achieved by the following operations:
5 5 aaaaa abbba ababa abbba aaaaa
24
7 10 xxxxxxxxxx ccccxxffff cxxcxxfxxx cxxxxxffff cxxcxxfxxx ccccxxfxxx xxxxxxxxxx
130