1181 C.Flag_牛客博客

$Description$
给定一个矩阵图案,找到有几种图形满足上面不等于中面,中面不等于下面.

$Solution$
处理高度数组 $h[i][j]$ ,宽度数组 $w[i][j]$ 即可.对答案贡献就是 $min( \frac {w[i][j]*(w[i][j]+1)}{2} )$ .

$Code$

#include<bits/stdc++.h>
#define sc scanf
using namespace std;
const int N=3e5+5;
const int mod=1e9+7;
typedef unsigned long long ull;
typedef long long ll;
template <typename it>int o(it a){cout<<a<<endl;return 0;}
int n,m;
ll ans=0;
int h[1005][1005],w[1005][1005];
char s[1005][1005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)sc("%s",s[i]+1);
    for(int j=1;j<=m;j++)
    for(int i=n;i>=1;i--)
    h[i][j]=(s[i][j]==s[i+1][j])?h[i+1][j]+1:1;
    for(int i=1;i<=n;i++)
    for(int j=m;j>=1;j--)
    w[i][j]=(s[i][j]==s[i][j+1])?w[i][j+1]+1:1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;){
            int x=i;
            if(x+h[x][j]<=n){
                int y=x+h[x][j];
                if(h[y][j]==h[x][j]){
                    if(y+h[y][j]<=n){
                        int z=y+h[y][j];
                        if(h[z][j]>=h[y][j]){
                            int len=m;
                            for(int k=x;k<z+h[y][j];k++)len=min(len,w[k][j]);
                            ans+=1ll*len*(len+1)/2;
                            j+=len;
                        }else j++;
                    }else j++;
                }else j++;
            }else j++;
        }
    }
    o(ans);
}