codeforces 1181 C. Flag

题意：n*m的图。子矩阵为3个窄条（相邻位置字母不同），则为旗。问图中有几个旗。

先dfs记录各位置向下多长和它是同一个字母dp1[i][j]。然后各位置为左上角的旗的宽度一定为3*dp1[i][j]。然后看看下面是否也行。如果行，mk1[i][j]记录dp1[i][j],mk2[i][j]记录3个字母是哪3个。

然后再从各位置dfs。如果和右边的mk1,mk2都相等，dp2[i][j]就等于右边的+1。所有dp2累加就是结果。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <stack>
#include <bitset>
#define mkp make_pair
#define err cout<<"err"<<endl
using namespace std;
const double EPS=1e-8;
typedef long long lon;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const lon SZ=3010,SSZ=SZ*SZ,APB=4,one=1;
const lon INF=0x3f3f3f3f,mod=1000000007;
lon n,m,dp1[SZ][SZ];
char ch[SZ][SZ];
lon mk1[SZ][SZ],mk2[SZ][SZ];
lon dp2[SZ][SZ];

void dfs1(int x,int y)
{
    if(ch[x+1][y]==ch[x][y])
    {
        dfs1(x+1,y);
        dp1[x][y]=dp1[x+1][y]+1;
    }
    else dp1[x][y]=1;
}

void dfs2(int x,int y)
{
    if(y>m)return;
    if(mk1[x][y]==mk1[x][y+1]&&mk2[x][y]==mk2[x][y+1])
    {
        dfs2(x,y+1);
        dp2[x][y]=mk1[x][y]!=0?dp2[x][y+1]+1:0;
    }
    else dp2[x][y]=mk1[x][y]!=0;
}

void init()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            cin>>ch[i][j];
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(!dp1[i][j])
            {
                if(ch[i][j]==ch[i+1][j])
                {
                    dfs1(i+1,j);
                    dp1[i][j]=dp1[i+1][j]+1;
                }
                else dp1[i][j]=1;
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            int len=dp1[i][j];
            int pos1=i+len;
            int pos2=i+len+len;
            if(dp1[pos1][j]==len&&dp1[pos2][j]>=len)
            {
                mk1[i][j]=len;
                int a=ch[i][j]-‘0‘;
                int b=ch[pos1][j]-‘0‘;
                int c=ch[pos2][j]-‘0‘;
                mk2[i][j]=a+b*26+c*26*26;
            }
        }
    }
    memset(dp2,-1,sizeof(dp2));
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(dp2[i][j]==-1)
            {
                if(mk1[i][j]==mk1[i][j+1]&&mk2[i][j]==mk2[i][j+1])
                {
                    dfs2(i,j+1);
                    dp2[i][j]=mk1[i][j]!=0?dp2[i][j+1]+1:0;
                }
                else dp2[i][j]=mk1[i][j]!=0;
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            //if(dp2[i][j])cout<<i<<" "<<j<<" "<<dp2[i][j]<<endl;
            res+=dp2[i][j];
        }
    }
    cout<<res<<endl;
}

void work()
{
    
}

//9 8
//wmmmmrww
//wmmmmrww
//wxxxxgww
//ggggxgww
//ssssmcww
//xxxxzcww
//wkwwwkww
//wcccccww
//wwwwwwww

void release()
{
    
}

int main()
{
    std::ios::sync_with_stdio(0);
    //freopen("d:\\1.txt","r",stdin);
    lon casenum;
    //cin>>casenum;
    //cout<<casenum<<endl;
    //for(lon tim=1;tim<=casenum;++tim)
    //for(lon tim=1;cin>>n;++tim)
    {
        //cout<<"Case #"<<tim<<": ";
        init();
        work();
        release();
    }
    return 0;
}