[COCI2009-2010#7] KRALJEVI
题目描述
Mirko 和 Slavko 在一个 $R \times C$ 的棋盘上游戏。他们各自在棋盘上摆放一定数量的王——王每步可以任选 $8$ 个方向中的一个移动 $1$ 步。现规定：
- 两个王之间的「距离」为其中一个王移动到另一个王所在棋格所需的最少步数。
- 一个玩家的「扩张度」为该玩家所有的王两两之间距离总和。
分别求出 Mirko 和 Slavko 的「扩张度」。
输入格式
第一行，两个整数 $R,C$。
接下来的 $R$ 行，每行 $C$ 个字符 $\texttt M$ / $\texttt S$ / $\texttt .$，分别表示 Mirko 的王、Slavko 的王和空位。数据保证每一方在棋盘上至少有一个王。
输出格式
输出两个整数，分别表示 Mirko 和 Slavko 的「扩张度」。
样例 #1
样例输入 #1
2 3
SMS
MMS样例输出 #1
3 5样例 #2
样例输入 #2
2 3
S.M
M..样例输出 #2
2 0样例 #3
样例输入 #3
4 5
M....
..S.M
SS..S
.M...样例输出 #3
10 13提示
【数据规模与约定】
- 对于 $20\%$ 的数据，棋盘上王的总数不超过 $5000$。
- 对于 $60\%$ 的数据，$R,C \le 300$。
- 对于 $100\%$ 的数据，$1 \le R,C \le 1000$。
【提示与说明】
题目译自 COCI 2009-2010 CONTEST #7 _Task 5 KRALJEVI_。
本题分值按 COCI 原题设置，满分 $120$。