← 返回题目列表

AtCoder · abc315_d

G. 神奇饼干

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有 H \times W 饼干 H 行和 W 列。
cookie 的颜色 i- 从顶部开始的行和 j左数第列用小写英文字母表示 c_{i,j}.

我们将执行以下过程。

1. 对于每一行,执行以下操作:如果该行中剩余两个或多个 cookie,并且它们都具有相同的颜色,则标记它们。

2. 对于每一列,执行以下操作:如果该列中剩余两个或多个 Cookie 并且它们都具有相同的颜色,则标记它们。

3、如果有标记的cookie,则全部删除并返回1;否则,终止程序。

查找过程结束时剩余的 cookie 数量。

约束

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

输入

输入由标准输入按以下格式给出:

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

4 3
aaa
aaa
abc
abd

示例输出 1

2

执行过程如下。

  • 1. 标记第一行和第二行的cookie。
  • 2. 在第一列中标记 cookie。
  • 3. 删除标记的 cookie。

此时,cookie 如下所示,其中 . 表示cookie已被删除的位置。

...
...
.bc
.bd
  • 1. 什么也不做。
  • 2. 在第二列中标记 cookie。
  • 3. 删除标记的 cookie。

此时,cookie 如下所示,其中 . 表示cookie已被删除的位置。

...
...
..c
..d
  • 1. 什么也不做。
  • 2. 什么都不做。
  • 3. 未标记 cookie,因此终止该过程。

最终剩余的 cookie 数量为 2.


示例输入 2

2 5
aaaaa
abcde

示例输出 2

4

示例输入 3

3 3
ooo
ooo
ooo

示例输出 3

0