Magical Cookies

题目描述

有 $H \times W$ 块饼干，排列成 $H$ 行 $W$ 列。
位于自顶向下第 $i$ 行、自左向右第 $j$ 列的饼干的颜色用小写英文字母 $c_{i,j}$ 表示。
我们要执行以下过程。

1. 对于每一行，执行如下操作：如果该行中剩下的饼干数不少于两个并且它们的颜色都相同，则将这些饼干标记。
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}$

输出格式

输出答案。

4 3
aaa
aaa
abc
abd

2

...
...
.bc
.bd

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

2 5
aaaaa
abcde

4

3 3
ooo
ooo
ooo

0

提示

$2 \leq H, W \leq 2000$ $c_{i,j}$ 是小写英文字母。该过程按如下方式进行。

1. 将第一行和第二行的饼干标记。
2. 将第一列的饼干标记。
3. 移除被标记的饼干。

此时，饼干看起来如下，其中 $.$ 表示该位置的饼干已被移除。

1. 无事发生。
2. 将第二列的饼干标记。
3. 移除被标记的饼干。

此时，饼干看起来如下，其中 $.$ 表示该位置的饼干已被移除。

1. 无事发生。
2. 无事发生。
3. 没有饼干被标记，因而终止该过程。

最终剩下的饼干数为 $2$.

标签: AtCoder|abc315D

来源

AtCoder|abc315D