https://codeforces.com/problemset/problem/1181/C
输入 n(≤1e3) m(≤1e3) 和一个 n 行 m 列的字符矩阵,元素都是小写字母。
定义「国旗」为一个 3h 行的子矩阵,前 h 行的字符都相同,中间 h 行的字符都相同,后 h 行的字符都相同,它们分别记作 A B C,要求 A 和 B 的字符不同,B 和 C 的字符不同(A 和 C 无要求)。
输出是国旗的子矩阵数量。
输入
4 3
aaa
bbb
ccb
ddd
输出
6
输入
6 1
a
a
b
b
c
c
输出
1
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef long long LL;
char g[N][N];
int n, m;
int h[N][N];
LL res;
int main ()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%s", g[i] + 1);
for(int i = n; i >= 1; i --){
for(int j = 1; j <= m; j ++){
if(g[i][j] == g[i + 1][j]) h[i][j] = h[i + 1][j] + 1; //dp所能向下一段最长的连续的字母的长度
else h[i][j] = 1;
}
}
for(int i = 1; i <= n; i ++){
for(int j = 1, ok = 0; j <= m; j ++){
int H = h[i][j];
if(i + 3 * H - 1 <= n && h[i + H][j] == H && h[i + 2 * H][j] >= H){
res ++;
if(h[i][j - 1] == H && g[i][j] == g[i][j - 1] && h[i + H][j - 1] == H && g[i + H][j - 1] == g[i + H][j] && h[i + 2 * H][j - 1] >= H && g[i + 2 * H][j - 1] == g[i + 2 * H][j])
{
ok ++;
}
else ok = 0;
}
else ok = 0;
res += ok;
}
}
cout << res << endl;
return 0;
}