分数: 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