Cod sursă (job #494304)

#include <bits/stdc++.h>

FILE *in = fopen("ssdj.in", "r"), *out = fopen("ssdj.out", "w") ;

const int MV = 1000 ;

char mat[MV + 3][MV + 3] ;
int ssdj[MV + 3][MV + 3] ;
int Stack[MV + 5] ;
int col[MV + 5] ;
int ans ;

int main() {
        int n, i, j, k, top ;
        fscanf(in, "%d\n", &n) ;
        for (i = 1 ; i <= n ; ++ i) {
                for (j = 1 ; j <= n ; ++ j) {
                        mat[i][j] = fgetc(in) ;
                }
                fgetc(in) ;
        }
        for (char letter = 'a' ; letter <= 'z' ; ++ letter) {
                for (i = 1 ; i <= n ; ++ i) {
                        for (j = 1 ; j <= n ; ++ j) {
                                if (mat[i][j] < letter) {
                                        ssdj[i][j] = ssdj[i - 1][j] + 1 ;
                                } else ssdj[i][j] = 0 ;
                        }
                }
                for (i = 2 ; i <= n ; ++ i) {
                        top = 0 ;
                        for (j = 1 ; j <= n ; ++ j) {
                                if (ssdj[i][j]) {
                                        while (top && Stack[top] >= ssdj[i][j]) {
                                                top -- ;
                                        }
                                        Stack[++ top] = ssdj[i][j] ;
                                        col[top] = j ;
                                } else {
                                        while (top && Stack[top] >= ssdj[i - 1][j] + 1) {
                                                top -- ;
                                        }
                                        for (k = 1 ; k <= top ; ++ k) {
                                                if (mat[i][j] == letter || mat[i - Stack[k]][col[k]] == letter) {
                                                        ans ++ ;
                                                }
                                        }
                                        top = 0 ;
                                }
                        }
                }
        }
        fprintf(out, "%d", ans) ;
}