链接: https://cses.fi/problemset/task/3415

板块: Counting Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个字母网格。你的任务是统计包含了所有字母的正方形子网格的数量。

输入

第一行包含两个整数 $n$ 和 $k$：网格的大小和字母的数量。字母为前 $k$ 个大写字母。

之后有 $n$ 行描述该网格，每行有 $n$ 个字母。

输出

输出子网格的数量。

数据范围

$1 \le n \le 3000$ $1 \le k \le 26$

样例输入

5 3
ABBBC
BBBBC
BCAAA
AAAAA
AAAAA

样例输出

15