#569. 「LibreOJ Round #11」Misaka Network 与测试

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cz_xuyixuan

题目描述

研究者们想要测试 Misaka Network,于是他们把 Misaka Network 中的所有妹妹们召集到了一起。

现在妹妹们排成了 N M 列,有的位置没有人。现在研究者们给每一个个体的超能力进行了评定,一共有三个能力等级:Level 1 低能力者Level 2 异能力者Level 3 超能力者。研究者们每次测试可以选取一个子矩形内的所有个体,为了保证高效,他们不希望这个矩形内存在空的位置。并且,为了保证稳定,他们希望这个矩形内所有个体的能力等级的平均值恰好为 2 。同时,每个个体最多只能参加一次测试,因此,多次测试选取的矩形应当不相交。

研究者们想知道他们最多能进行多少次测试。

输入格式

第一行两个整数 N M

接下来 N 行每行 M 个字符,每个字符表示了队列中对应位置的个体。

1 表示 Level 1 低能力者2 表示 Level 2 异能力者3 表示 Level 3 超能力者* 表示一个空的位置。

输出格式

一行一个整数,表示最多能够进行多少次测试。

样例

样例输入 1

2 3
31*
*13

样例输出 1

2

样例输入 2

6 6
23311*
**13**
11*233
13*223
***133
331***

样例输出 2

9

样例输入 3

2 50
21111121332233123311312211231333122233133212221212
21332123132223111331233121122331133311112121331311

样例输出 3

51

数据范围与提示

对于所有数据 1 \leq N \times M \leq 10^5 ,队列中仅包含 123* 四种字符。

子任务编号 分值 N \times M 特殊性质
1 5 \leq 10^5 队列中不存在 1
2 15 \leq 1000 N=1
3 \leq 2000 N=2
4 35 队列中不存在 *
5 15 -
6 \leq 10^5