Cod sursa(job #1729505)

Utilizator Athena99Anghel Anca Athena99 Data 14 iulie 2016 22:16:07
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <string>

using namespace std;

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

const int nmax= 1000;
const int sigma= 26;

bool d[nmax+1][nmax+1];
int v[sigma], b[nmax+1][nmax+1];

string a[nmax+1], s;

int main(  ) {
    int n, m;
    fin>>n>>m;
    for ( int i= 1; i<=n; ++i ) {
        fin>>a[i];
        for ( int j= 1; j<=n; ++j ) {
            d[i][j]= 1;
        }
    }
    for ( int i= 1; i<=m; ++i ) {
        fin>>s;
        for ( int j= 0; j<m; ++j ) {
            ++v[s[j]-'a'];
        }
    }

    for ( int k= 0; k<sigma; ++k ) {
        for ( int i= 1; i<=n; ++i ) {
            for ( int j= 1; j<=n; ++j ) {
                b[i][j]= b[i-1][j]+b[i][j-1]-b[i-1][j-1];
                if ( a[i][j-1]==k+'a' ) {
                    ++b[i][j];
                }

                if ( i<m || j<m || b[i][j]-b[i-m][j]-b[i][j-m]+b[i-m][j-m]!=v[k] ) {
                    d[i][j]= 0;
                }
            }
        }
    }

    int sol= 0;
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=n; ++j ) {
            sol+= d[i][j];
        }
    }

    fout<<sol<<"\n";

    return 0;
}