Mr. Ham has a matrix of size $$$ n \times m $$$, where each cell is filled with a color value $$$c_{i,j}$$$. Mr. Ham is interested in the relationships between cells of the same color and wants to calculate the sum of Manhattan distances between all pairs of cells with the same color.
The Manhattan distance between two cells $$$ (x_1, y_1) $$$ and $$$ (x_2, y_2) $$$ is given by $$$ d_M = \left|x_1 - x_2\right| + \left|y_1 - y_2\right| $$$.
Formally, please compute:
$$$$$$\text{Total Sum} = \sum_C \sum_{(x_i, y_i) \in S_C} \sum_{(x_j, y_j)\in S_C} \left|x_i-x_j\right|+\left|y_i-y_j\right|$$$$$$
Here, $$$C$$$ denotes the set of all distinct colors. $$$ S_C $$$ denotes the set of coordinates $$$ (x, y) $$$ with the color value equal to the specified color $$$C$$$.
The first line contains two integers $$$ n $$$ and $$$ m $$$ (1$$$\leq n, m \leq 1000$$$), representing the number of rows and columns in the matrix.
The following contains n lines. Each line $$$i$$$ contains $$$m$$$ space-separated integers $$$c_{i,j}$$$ ($$$1 \leq c_{i,j} \leq 10^9$$$), representing the color values in the matrix.
Output a single integer, the sum of Manhattan distances for all pairs of cells with the same color.
2 21 12 2
4
4 41 3 2 42 1 2 31 3 3 23 2 1 4
152
In the first example, the distinct color values are $$$1$$$ and $$$2$$$.
Name |
---|