Cod sursă (job #301673)

#include <cstdio>

using namespace std;

#define maxn 1010

int n, hh, st0, sol;
char v[maxn][maxn];
int st[maxn], pz[maxn], h[maxn][maxn];

int main()
{
    freopen("ssdj.in", "r", stdin);
    freopen("ssdj.out", "w", stdout);
    scanf("%d\n", &n);
    for(int i=1; i<=n; ++i)
        scanf("%s", v[i]+1);
    for(char mx = 'a'; mx <= 'z'; ++mx)
    {
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                if(v[i][j]>=mx)
                    h[i][j]=0;
                else
                    h[i][j]=h[i-1][j]+1;

        for(int i=2; i<=n; ++i)
        {
            st0=0;
            for(int j=1; j<=n; ++j)
            {
                if(h[i][j]>0)
                {
                    while(st0>0 && st[st0]>=h[i][j])
                        --st0;
                    st[++st0]=h[i][j];
                    pz[st0]=j;
                }
                else
                {
                    hh=h[i-1][j]+1;

                    while(st0>0 && st[st0]>=hh)
                        --st0;

                    for(int k=1; k<=st0; ++k)
                        if(v[i][j]==mx || v[i-st[k]][pz[k]]==mx)
                            ++sol;
                    st0=0;
                }
            }
        }
    }
    printf("%d\n", sol);
    return 0;
}