Cod sursa(job #1828349)

Utilizator dnprxDan Pracsiu dnprx Data 13 decembrie 2016 09:39:14
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>
#define nmax 1005
using namespace std;

char a[nmax][nmax], b[nmax][nmax];
int sume[nmax][nmax];
int sumep[nmax][nmax];
int n, m;
int S, SP;

void Citire()
{
    int i;
    ifstream fin("matrix.in");
    fin >> n >> m;
    for (i = 1; i <= n; i++)
        fin >> (a[i] + 1);
    for (i = 1; i <= m; i++)
        fin >> (b[i] + 1);
    fin.close();
}

void Rezolva()
{
    int i, j, x, ans;
    int w, wp;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= m; j++)
        {
            x = b[i][j] - 'a' + 1;
            S += x;
            SP += (x * x);
        }
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
        {
            x = a[i][j] - 'a' + 1;
            sume[i][j] = sume[i-1][j] + sume[i][j-1] + x - sume[i-1][j-1];
            sumep[i][j] = sumep[i-1][j] + sumep[i][j-1] + x * x - sumep[i-1][j-1];
        }
    ans = 0;
    for (i = m; i <= n; i++)
        for (j = m; j <= n; j++)
        {
           w = sume[i][j] - sume[i - m][j] - sume[i][j - m] + sume[i - m][j - m];
           wp = sumep[i][j] - sumep[i - m][j] - sumep[i][j - m] + sumep[i - m][j - m];
           if (w == S && wp == SP) ans++;
        }
    ofstream fout("matrix.out");
    fout << ans << "\n";
    fout.close();
}

int main()
{
    Citire();
    Rezolva();
    return 0;
}