Cod sursa(job #1520521)

Utilizator cristina_borzaCristina Borza cristina_borza Data 8 noiembrie 2015 22:09:06
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int N , M , sol;
char mat1[1005][1005] , mat2[1005][1005];
int lit1[1005][1005] , lit2[1005][1005] , ok[1005][1005];

int main() {
    f >> M >> N;

    for(int i = 1 ; i <= M ; ++i) {
        for(int j = 1 ; j <= M ; ++j) {
            f >> mat1[i][j];
            ok[i][j] = 1;
        }
    }

    for(int i = 1 ; i <= N ; ++i) {
        for(int j = 1 ; j <= N ; ++j) {
            f >> mat2[i][j];
        }
    }

    for(char c = 'a' ; c <= 'z' ; ++c) {
        memset(lit1 , 0 , sizeof(lit1));
        memset(lit2 , 0 , sizeof(lit2));

        for(int i = 1 ; i <= M ; ++i) {
            for(int j = 1 ; j <= M ; ++j) {
                lit1[i][j] = lit1[i - 1][j] + lit1[i][j - 1] - lit1[i - 1][j - 1] + (mat1[i][j] == c);
            }
        }

        for(int i = 1 ; i <= N ; ++i) {
            for(int j = 1 ; j <= N ; ++j) {
                lit2[i][j] = lit2[i - 1][j] + lit2[i][j - 1] - lit2[i - 1][j - 1] + (mat2[i][j] == c);
            }
        }

        for(int i = N ; i <= M ; ++i) {
            for(int j = N ; j <= M ; ++j) {
                int aux1 = lit1[i][j] - lit1[i - N][j] - lit1[i][j - N] + lit1[i - N][j - N];
                int aux2 = lit2[N][N];

                ok[i][j] = (ok[i][j] & (aux1 == aux2));
            }
        }
    }

    for(int i = N ; i <= M ; ++i) {
        for(int j = N ; j <= M ; ++j) {
            sol += (ok[i][j] == 1);
        }
    }

    g << sol;
    return 0;
}