Cod sursa(job #3161936)

Utilizator DenisBadarauDenisBadarau DenisBadarau Data 28 octombrie 2023 10:40:16
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;

/**
4 2
bbba     0 0 1 0
ccaa =>  0 1 0 0
abab     0 1 0 1
baac     1 0 0 2

aa => s = 0+0+1+1=2
bb

aa    Y = 0+0+9+9 = 18
dd => X = 0+0+3+3=6

bb    s = 1+1+2+2 = 6
cc => sp=1+1+4+4 = 10
*/
ifstream fin("matrix.in");
ofstream fout("matrix.out");

int X, Y, m, cnt;
int s[1002][1002], sp[1002][1002], n;

int main()
{
    int i, j, x, y;
    char ch;
    /// citire si formare sume partiale
    fin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
        {
            fin >> ch;
            x = ch - 'a' + 1;
            s[i][j] = s[i-1][j]+s[i][j-1]+
                x-s[i-1][j-1];
            sp[i][j] = sp[i-1][j]+sp[i][j-1]+
                x*x-sp[i-1][j-1];
        }
    X = Y = 0;
    for (i = 1; i <= m; i++)
        for (j = 1; j <= m; j++)
        {
            fin >> ch;
            x = ch - 'a' + 1;
            X += x;
            Y += x * x;
        }
    /// contorizare
    for (i = m; i <= n; i++)
        for (j = m; j <= n; j++)
        {
            x = s[i][j]-s[i-m][j]-s[i][j-m]
                + s[i-m][j-m];
            y = sp[i][j]-sp[i-m][j]-sp[i][j-m]
                + sp[i-m][j-m];
            if (x == X && y == Y)
                cnt++;
        }
    fout << cnt << "\n";
    return 0;
}