You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC315D] Magical Cookies

题面翻译

给出 $H \times W$ 的地图，不断进行以下操作：

1. 选定某行，若这行字母数 $\ge 2$，并且全是相同的，将所有这些字母标记。
2. 选定某列，若这列字母数 $\ge 2$，并且全是相同的，将所有这些字母标记。
3. 把目前标记的字母删除，若无删除，结束操作，否则重新跳回操作 1。

$1 \le H,W \le 2000$。求最后操作完成后还剩多少个字母。

题目描述

There are H×W cookies in H rows and W columns. The color of the cookie at the i-row from the top and j-th column from the left is represented by a lowercase English letter ci,j.

We will perform the following procedure.

1. For each row, perform the following operation: if there are two or more cookies remaining in the row and they all have the same color, mark them.
2. For each column, perform the following operation: if there are two or more cookies remaining in the column and they all have the same color, mark them.
3. If there are any marked cookies, remove them all and return to 1; otherwise, terminate the procedure.

Find the number of cookies remaining at the end of the procedure.

输入格式

输入格式如下：

$H$ $W$ $c_{1,1}$ $c_{1,2}$ $\ldots$ $c_{1,W}$ $c_{2,1}$ $c_{2,2}$ $\ldots$ $c_{2,W}$ $\vdots$ $c_{H,1}$ $c_{H,2}$ $\ldots$ $c_{H,W}$

输出格式

输出一个整数表示最后的答案。

样例 #1

样例输入 #1

4 3
aaa
aaa
abc
abd

样例输出 #1

2

样例 #2

样例输入 #2

2 5
aaaaa
abcde

样例输出 #2

4

样例 #3

样例输入 #3

3 3
ooo
ooo
ooo

样例输出 #3

0

提示

数据范围

• $2\ \leq\ H,\ W\ \leq\ 2000$
• $c_{i,j}$ 是小写英文字母

样例解释1

按以下顺序进行操作。 - 1. 操作1，$1,\ 2$ 行所有字母被标记。 - 2. 操作2，$1$ 列所有字母被标记。 - 3. 操作3，将所有被标记字母删除。 用"."来替代被删除的字母，可以得到矩阵变成了： ... ... .bc .bd - 1. 操作1，没有字母被标记。 - 2. 操作2，$2$ 列所有字母被标记。 - 3. 将所有被标记字母删除。 用"."来替代被删除的字母，可以得到矩阵变成了： ... ... ..c ..d - 1.操作1，没有字母被标记。 - 2. 操作2，没有字母被标记。 - 3. 操作3，没有字母被标记，所以没有字母被删除。最終剩下 $2$ 个字母。