Codeforces Round #662 (Div. 2) D. Rarity and New Dress

发表于 分类于

链接

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

题意

问 $n*m$ 的矩阵中，有多少合法的菱形，合法的条件：各单元格元素相同并且不越界

合法的例子：

思路

设 $dp[i][j]$ 为以 $(i,j)$ 为最底块的合法的菱形的个数

$dp[i][j]=1+min(dp[i-1][[j-1],dp[i-1][j],dp[i-1][j+1],dp[i-2][j])$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
//head
const int N=2005;
int n,m,dp[N][N],res;
char s[N][N];
bool valid(int x,int y) {
    if(x>=1&&x<=n&&y>=1&&y<=m) return true;
    return false;
}
int judge(int x,int y,char c) {
    if(!valid(x,y)) return 0;
    if(s[x][y]!=c) return 0;
    return dp[x][y];
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            char c=s[i][j];
            int now=judge(i-1,j-1,c);
            now=min(now,judge(i-1,j,c));
            now=min(now,judge(i-1,j+1,c));
            now=min(now,judge(i-2,j,c));
            now++;
            dp[i][j]=now;
            res+=now;
        }
    printf("%d\n",res);
    return 0;
}