P8075 [COCI 2009/2010 #7] KRALJEVI

Mirko and Slavko are playing a game on an $R \times C$ chessboard. Each of them places some kings on the board. A king can move $1$ step each move in any of the $8$ directions. The rules are: - The “distance” between two kings is the minimum number of moves needed for one king to move to the square of the other king. - A player’s “spread” is the sum of distances over all pairs of that player’s kings. Compute the “spread” for Mirko and for Slavko.

The first line contains two integers $R, C$. The next $R$ lines each contain $C$ characters $\texttt M$ / $\texttt S$ / $\texttt .$ , representing Mirko’s kings, Slavko’s kings, and empty squares. The testdata guarantees that each side has at least one king on the board.

Output two integers, representing the “spread” of Mirko and the “spread” of Slavko, respectively.

**Constraints** - For $20\%$ of the testdata, the total number of kings on the board does not exceed $5000$. - For $60\%$ of the testdata, $R, C \le 300$. - For $100\%$ of the testdata, $1 \le R, C \le 1000$. **Hints and Notes** **This problem is translated from [COCI 2009-2010](https://hsin.hr/coci/archive/2009_2010/) [CONTEST #7](https://hsin.hr/coci/archive/2009_2010/contest7_tasks.pdf) _Task 5 KRALJEVI_.** **The score of this problem follows the original COCI setting, with a full score of $120$.** Translated by ChatGPT 5