Cod sursa(job #3266143)

Utilizator ana_maria_772Toc Ana-Maria ana_maria_772 Data 6 ianuarie 2025 00:15:49
Problema Matrix Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <cstring>
using namespace std;

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

int n, m, cnt, x, fv[50];
char v[1001];
struct matrice {
    int s[1001][1001];
} t[50];

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