Cod sursa(job #3266135)

Utilizator ana_maria_772Toc Ana-Maria ana_maria_772 Data 5 ianuarie 2025 21:29:41
Problema Matrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <cstring>
using namespace std;

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

int n, m, cnt, x, s[1001][1001], fo[50], fv[50];
char v[1001], mat[1001][1001];

int main() {
    cin>>n>>m;
    for (int i=1; i<=n; i++)
    {
        cin>>(mat[i]+1);
        for (int j=1; j<=n; j++)
            s[i][j]= s[i-1][j] + s[i][j-1] - s[i-1][j-1] + (mat[i][j]-'a'+1);
    }
    for (int i=1; i<=m; i++)
    {
        cin>>v;
        for (int j=0; j<m; j++)
            x+= (v[j]-'a'+1), fv[v[j]-'a'+1]++;
    }
    
    for (int i=1; i<n-m+2; i++)
        for (int j=1; j<n-m+2; j++)
        {
            int i2= i+m-1, j2= j+m-1;
            int sum= s[i2][j2] - s[i-1][j2] - s[i2][j-1] + s[i-1][j-1];
            if (sum==x)
            {
                for (int k=i; k<=i2; k++)
                    for (int q=j; q<=j2; q++)
                        fo[mat[k][q]-'a'+1]++;
                bool ok=1;
                for (int k='a'-'a'+1; k<='z'-'a'+1; k++)
                {
                    if (fo[k]!=fv[k])
                        ok=0;
                    fo[k]= 0;
                }
                if (ok) 
                    cnt++;
            }
        }
    cout<<cnt;
    return 0;
}