D

题：https://codeforces.com/contest/1393/problem/D

题意：给出n*n的字符矩阵，问矩阵中有多少个相同字符的“斜正方形”。

分析：对于每一个位置我们设dp[i][j]为位置[i][j]向上能最多”延申“的”斜正方形边长“，那么总的答案就是所有位置的dp值之和。

　　　转移分为当前位置[i][j]与上面四个位置（[i-1][j]、[i-1][j-1]、[i-1][j+1]、[i-2][j]）能否形成“斜正方形”：

　　　　　若能，则取min（dp[i-1][j-1]、dp[i-1][j+1]、dp[i-2][j]）+1，这里可以简单画个图理解一下当前[i][j]高度的“延申”只是依赖于这三个位置的dp值，

　　　　　若不能则dp[i][j]=1;

#include <bits/stdc++.h>
using namespace std;
const int M=2e3+10;
typedef long long ll;
char a[M][M];
int f[M][M],n,m,i,j;
ll ans=0;
int main(){
    scanf("%d%d",&n,&m);
    for(i=2;i<=n+1;i++)
        scanf("%s",a[i]+1);
    for(i=2;i<=n+1;i++)
        for (j=1;j<=m;j++){
            if ((a[i][j]!=a[i-1][j]) || (a[i][j]!=a[i-1][j-1]) || (a[i][j]!=a[i-1][j+1]) || (a[i][j]!=a[i-2][j])) f[i][j]=1;
                else f[i][j]=1+min(min(f[i-1][j-1],f[i-1][j+1]),f[i-2][j]);
            ans+=1LL*f[i][j];
        }
    printf("%I64d
",ans);
    return 0;
}