[CF1393D] Rarity and New Dress

Description

给定一个 (n imes m) 的网格，每个格子有一个颜色，问有多少个同色菱形。(n,m le 2000)

Solution

类似“最大正方形”的套路，设 (f[i][j]) 表示以 ((i,j)) 点为下顶点的菱形的最大边长，转移时考虑 ((i,j),(i-1,j),(i-2,j),(i-1,j-1),(i-1,j+1)) 这五个点是否相等，如果相等则从 (f[i-1][j],f[i-2][j],f[i-1][j-1],f[i-1][j+1]) 中取最小值转移过来即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 2005;

char a[N][N];
int f[N][N],n,m;

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i]+1;
    
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=1;

    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(i>1 && j>1)
    {
        if(a[i-1][j-1]==a[i-1][j] && a[i-1][j+1]==a[i-1][j] && a[i-2][j]==a[i-1][j] && a[i][j]==a[i-1][j])
        {
            f[i][j]=max(f[i][j],min(min(f[i-1][j-1],f[i-1][j+1]),min(f[i-1][j],f[i-2][j]))+1);
        }
    }

    int ans=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans+=f[i][j];

    cout<<ans<<endl;
    return 0;
}