CF1393D Rarity and New Dress 题解

题意：

cxy 要从一块 $n\times m$ 的布料上裁一块菱形做裙子（不是给自己做。

这一块布料由 $n\times m$ 个颜色块组成，要满足裁下的菱形必须由若干相同的颜色块组成。

求有多少种裁法。

注：一个方格也算一个菱形。

Examples of proper dress patterns:
Examples of improper dress patterns:
The first one consists of multi-colored scraps, the second one goes beyond the bounds of the piece of fabric, the third one is not a square with sides forming a $45^{\circ}$ angle with sides of the piece of fabric.

Rarity wonders how many ways to cut out a dress pattern that satisfies all the conditions that do exist. Please help her and satisfy her curiosity so she can continue working on her new masterpiece!

输入格式：

The first line contains two integers $n$ and $m$ ( $1\le n, m \le 2000$ ). Each of the next $n$ lines contains $m$ characters: lowercase English letters, the $j$ -th of which corresponds to scrap in the current line and in the $j$ -th column. Scraps having the same letter share the same color, scraps having different letters have different colors.

输出格式：

Print a single integer: the number of ways to cut out a dress pattern to satisfy all of Rarity’s conditions.

看上去很难，其实很简单。我们只需要找到所有极大的菱形就可以了，

而每个菱形都可以由中心和直径决定，因此考虑维护每个点最远能到哪，稍微算算就好啦。

时间复杂度 $\mathcal{O}(nm)$

代码：

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e3 + 15))

char c[N][N];
int n,m,ans,U[N][N],D[N][N],L[N][N],R[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> (c[i] + 1);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            U[i][j] = (c[i][j] == c[i - 1][j] ? U[i - 1][j] + 1 : 1);
    for(int i = n; i >= 1; i--)
        for(int j = 1; j <= m; j++)
            D[i][j] = (c[i][j] == c[i + 1][j] ? D[i + 1][j] + 1 : 1);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
            if(c[i][j] != c[i][j - 1]) L[i][j] = 1;
            else L[i][j] = min({U[i][j], D[i][j], L[i][j - 1] + 1});
        for(int j = m; j >= 1; j--)
            if(c[i][j] != c[i][j + 1]) R[i][j] = 1;
            else R[i][j] = min({U[i][j], D[i][j], R[i][j + 1] + 1});
        for(int j = 1; j <= m; j++) ans += min(L[i][j], R[i][j]);
    }
    cout << ans << '\n';
    return 0;
}