AT_abc315_d [ABC315D] Magical Cookies

题目描述

有 $H \times W$ 块饼干，排成 $H$ 行 $W$ 列。
第 $i$ 行第 $j$ 列的饼干颜色用小写英文字母 $c_{i,j}$ 表示。

现在要进行如下操作：

1. 对每一行进行如下操作：如果该行剩下的饼干数量不少于 $2$ 且颜色全部相同，则给这些饼干做上标记。
2. 对每一列进行如下操作：如果该列剩下的饼干数量不少于 $2$ 且颜色全部相同，则给这些饼干做上标记。
3. 如果有被标记的饼干，则将它们全部移除，然后回到第 1 步；如果没有，则操作结束。

请你求出操作结束时剩下的饼干数量。

输入格式

输入按以下格式从标准输入读入。

$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$、$2$ 行的饼干做上标记。
• 第 2 步，对第 $1$ 列的饼干做上标记。
• 第 3 步，将做了标记的饼干全部移除。此时饼干如下，用 . 表示已移除的位置。

...
...
.bc
.bd

• 第 1 步，不做任何操作。
• 第 2 步，对第 $2$ 列的饼干做上标记。
• 第 3 步，将做了标记的饼干全部移除。此时饼干如下，用 . 表示已移除的位置。

...
...
..c
..d

• 第 1 步，不做任何操作。
• 第 2 步，不做任何操作。
• 第 3 步，没有做标记的饼干，操作结束。

最终剩下的饼干数量为 $2$。

由 ChatGPT 4.1 翻译