思路:前缀和+滑动窗口

1.正方形本质上就是两个在同一个对角线上的点构成的矩阵。所以先把下标根据对角线归类成不同序列,例如一个3 × 3的矩阵:

red

red

red

python选手使用pypy3提交

题目内容

给小红一个$n×n$的方阵，第$i$行第$j$列的元素是$r,e,d$中的一个。

定义一个矩阵权值为这个矩阵出现的$r,e,d$数量的最小值。

现在有一个值$myval$，现在想请小红计算出，有多少个子方阵的矩阵权值不小于$myval$。

一个行数与列数相等的矩阵称为方阵。

补充说明

函数第一个参数输入一个大小为$n×n(1≤n≤1000)$，且仅由$r,e,d$构成的$vector<string>$代表矩阵$a$。

函数第二个参数输入一个整数$myval(1≤myval ≤10^9)$代表值。

样例1

输入

3 2
red
red
red

输出

1

说明

只有整个$3×3$方阵才是合法的。

样例2

输入

3 1
red
edr
dre

输出

5