Cod sursa(job #557030)

Utilizator SpiderManSimoiu Robert SpiderMan Data 16 martie 2011 13:48:51
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
# include <bitset>
# include <cstdio>

const char *FIN = "matrix.in", *FOU = "matrix.out" ;
const int MAX = 1005, SG = 26 ;

std :: bitset < MAX > sol[MAX] ;
char S[MAX][MAX] ;
int dp[MAX][MAX] ;
int F[SG] ;
int N, M, sl ;


int main ( void ) {
    freopen ( FIN, "r", stdin ) ;

    scanf ( "%d %d", &N, &M ) ;
    for ( int i = 1; i <= N; ++i ) {
        scanf ( "%s", S[i] + 1 ) ;
    }
    for ( int i = 1; i <= M; ++i ) {
        scanf ( "%s", S[0] + 1 ) ;
        for ( int j = 1; j <= M; ++j ) {
            ++F[ S[0][j] - 'a' ] ;
        }
    }
    for ( int i = M; i <= N; ++i ) {
        for ( int j = M; j <= N; ++j ) {
            sol[i][j] = 1 ;
        }
    }
    for ( int c = 0; c < SG; ++c ) {
        for ( int i = 1; i <= N; ++i ) {
            for ( int j = 1; j <= N; ++j ) {
                dp[i][j] = ( c + 'a' == S[i][j] ) + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] ;
                if ( i >= M && j >= M && sol[i][j] ) {
                    sol[i][j] = F[c] == dp[i][j] - dp[i - M][j] - dp[i][j - M] + dp[i - M][j - M] ;
                }
            }
        }
    }

    for ( int i = M; i <= N; ++i ) {
        for ( int j = M; j <= N; ++j ) {
            sl += sol[i][j] ;
        }
    }
    fprintf ( fopen ( FOU, "w" ), "%d", sl ) ;
}