Cod sursă (job #362266)

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <stack>

using namespace std;

const int N = 1002 ;

int noLin ;
char allChar[ N ][ N ];
int valUnderBelow [ N ][ N ] ;
stack < int > stkHeights ;
stack < int > stkCol ;
int noSol ;

void preCalcDP( char crChar ){

    for  ( int i = 1 ; i <= noLin ; i++ ){
        for ( int j = 1 ; j <= noLin ; j++ ){
            valUnderBelow [ i ][ j ] = 0 ;
            if ( allChar [ i ] [ j ] < crChar ){
                valUnderBelow [ i ][ j ] = valUnderBelow [ i - 1 ][ j ] + 1 ;
            }
        }
    }

}

int main(){

    freopen("ssdj.in","r",stdin);
    freopen("ssdj.out","w",stdout);

    scanf("%d", &noLin );

    for ( int i = 1 ; i <= noLin ; i++ ){
        scanf("%s", allChar[ i ] + 1 );
    }

    for ( char crChar = 'a' ; crChar <= 'z' ; crChar ++ ){
        preCalcDP( crChar );

        for ( int i = 2 ; i <= noLin ; i++ ){

            while ( !stkHeights.empty()  ){
                stkHeights.pop();
                stkCol.pop();
            }

            for ( int j = 1 ; j <= noLin ; j++ ){

                if ( valUnderBelow [ i ][ j ] ){

                    while ( !stkHeights.empty() && stkHeights.top() >= valUnderBelow [ i ][ j ] ){
                        stkHeights.pop() ;
                        stkCol.pop();
                    }
                    stkHeights.push( valUnderBelow [ i ][ j ] );
                    stkCol.push( j );
                }else{

                    while ( !stkHeights.empty() && stkHeights.top() >= valUnderBelow [ i - 1 ][ j ] + 1 ){
                        stkHeights.pop() ;
                        stkCol.pop();
                    }

                    while ( !stkHeights.empty() ){
                        if ( allChar [ i ][ j ] == crChar || allChar [ i - stkHeights.top() ][ stkCol.top() ] == crChar ){
                            noSol ++;
                        }
                        stkHeights.pop() ;
                        stkCol.pop() ;
                    }

                }

            }


        }

    }
    printf("%d",noSol );

    return 0;
}