Cod sursa(job #1335931)

Utilizator felixiPuscasu Felix felixi Data 6 februarie 2015 07:56:43
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream in("matrix.in");
ofstream out("matrix.out");

const int NMAX = 1001;

int f[NMAX];
int d[NMAX][NMAX] , s[NMAX][NMAX];
char a[NMAX][NMAX] , c[NMAX][NMAX];
int N, M, Ans = 0;

int main() {
    in >> N >> M;
    for( int i = 1;  i <= N;  ++i ) {
        c[i][0] = '#';
        in >> (c[i]+1);
    }
    for( int i = 1;  i <= M;  ++i ) {
        a[i][0] = '#';
        in >> (a[i]+1);
        for( int j = 1;  j <= M;  ++j )  ++f[ a[i][j] - 'a' + 1 ];
    }

    memset( d, 1, sizeof(d) );
    for( int val = 'a'-'a'+1;  val <= 'z'-'a'+1;  ++val ) {
        memset( s, 0, sizeof(s) );
        for( int i = 1;  i <= N;  ++i ) {
            for( int j = 1;  j <= N;  ++j ) {
                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + ( c[i][j] == (char)(val + 'a' - 1) );
                if( i >= M && j >= M ) {
                    d[i][j] = ( d[i][j] && (s[i][j] - s[i-M][j] - s[i][j-M] + s[i-M][j-M] == f[val]) );
                    if( val == (int)('z'-'a'+1) )  Ans += d[i][j];
                }
            }
        }
    }

    out << Ans << '\n';

    return 0;
}