Public Judge

pjudge

Time Limit: 6 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

题目描述

当今世界,科技飞速发展,AI 也会绘画了!不过本题中你要解决的任务比绘画简单很多,给你一张画,你要求出其中有多少个“圈”。

一幅画可以抽象为一个 $n$ 行 $m$ 列的字符数组 $a_{i,j}\ (1\le i\le n,1\le j\le m)$,其中仅包含小写字母。如果一对字符数组中的位置 $(x_1,y_1),(x_2,y_2)$ 满足:

  • $1\le x_1\lt x_2\le n,1\le y_1\lt y_2\le m$。
  • $\forall i\in [x_1,x_2],j\in [y_1,y_2],a_{i,y_1}=a_{x_1,j}=a_{x_2,j}=a_{i,y_2}$。

我们就说有一个以 $(x_1,y_1)$ 为左上角、$(x_2,y_2)$ 为右下角的“圈”。比如,下图中的所有 b 就构成一个圈:

aaaaaaaaaaa
aabbbbbbbaa
aabaaaaabaa
aabaaaaabaa
aabbbbbbbaa

请你输出给定的字符数组中“圈”的数量。

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行,每行 $m$ 个小写字母,第 $i$ 行的第 $j$ 个小写字母是 $a_{i,j}$。

输出格式

输出一个非负整数表示字符数组中“圈”的个数。

样例输入输出

样例输入 1

3 5
zzzzz
zxzxz
zzzzz

样例输出 1

3

样例 1 解释

下面我们分别在原图中用 * 标注出了三个“圈”:

***zz    zz***    *****
*x*xz    zx*x*    *xzx*
***zz    zz***    *****

样例 2

见下发文件。

本组样例满足子任务 $1$ 的性质。

样例 3

见下发文件。

本组样例满足子任务 $1$ 的性质。

样例 4

见下发文件。

本组样例满足子任务 $2$ 的性质。

样例 5

见下发文件。

本组样例满足子任务 $2$ 的性质。

样例 6

见下发文件。

本组样例满足子任务 $2$ 的性质。

样例 7

见下发文件。

本组样例满足子任务 $4$ 的性质。

样例 8

见下发文件。

本组样例满足子任务 $6$ 的性质。

数据范围

本题采用捆绑测试,你需要通过一个子任务的所有测试点才能得到子任务的分数。

对于所有测试点,$1\le n,m\le 2000$。详细数据范围如下表。

子任务编号 $n,m\le $ 特殊性质 分数
$1$ $5$ 矩阵中所有字母均在 ab 中随机生成 $5$
$2$ $2000$ $nm\le 40000$ $10$
$3$ 矩阵中只存在字母 a $10$
$4$ 矩阵中所有字母均在 ab 中随机生成 $15$
$5$ $400$ $25$
$6$ $2000$ $35$

时间限制:$6\texttt{s}$

空间限制:$1024\texttt{MB}$